KMP is for searching,what's the one for replacing?
+3
A:
"Replacing" is nothing more than correct copying of the right (non-matched) substrings, while inserting the substitution for the matched pieces (which is a pretty trivial task, quite independent of algorithmic issues!-). So, if you know that KMP is the best algorithm for the searching subtask (not as cut-and-dried an issue as you present it, in the general case), it will also be best for "replacing" (especially if you "replace" by making a new string, as you do in languages with immutable strings like Java and Python -- but, nevertheless, even with a mutable-strings language -- just identify matches first, THEN do the replaces;-).
Alex Martelli
2009-12-15 04:47:48
But "replace" can't be done in O(1) without allocating more memories
2009-12-15 04:48:47
Neither can search.
Alex
2009-12-15 04:54:30
Don't forget the worst case complexity is O(KMP)*O(replace).
2009-12-15 04:59:01
@unknown, O(1) is crazy talk -- of course you can't insert an N-long string into another string, in anything less than O(N)!. So I'm not sure what you're talking about. Please clarify if you need in-place changes (or a modified copy as Java or Python would afford) and what letters you're using for (a) length of "haystack" string getting the replacements, (b) length of old substring getting replaced, (c) length of new replacement substring.
Alex Martelli
2009-12-15 05:00:29
you can insert in O(1) if the strings are implemented as lists and you don't need an extra copy of the inserted string.
Nick D
2009-12-15 05:13:18
@Nick D: linked lists give you O(1) insertion, but set a lower bound of O(N) for the search and require O(M) to remove the string being replaced. Random access allows you to search with BM or BMH, with approximately O(N/M) complexity. Unless M is dependably small, or you expect a high density of matches, the linked list will lose.
Jerry Coffin
2009-12-15 05:29:11
@Jerry Coffin, I agree. I mentioned O(1) insertion because it depends on the implementation. But generally, random access is much better because *insert* operation doesn't happen very often.
Nick D
2009-12-15 05:51:51