All Questions
Tagged with string-matching runtime-analysis
2 questions
2
votes
1
answer
75
views
Complexity of right-to-left Knuth-Morris-Pratt algorithm
Suppose we modify the Knuth-Morris-Pratt string-matching algorithm to scan the pattern right-to-left a la Boyer-Moore, and consequently apply the shift rule on the right side of the cursor instead of ...
- 195
8
votes
3
answers
12k
views
What is the expected time complexity of checking equality of two arbitrary strings?
The simple (naive?) answer would be O(n) where n is the length of the shorter string. Because in the worst case you must compare every pair of characters.
So far so good. I think we can all agree that ...
- 297