Algorithms and Data Structures · Senior · Question 22 of 75
How does KMP achieve O(n + m) string search?
- 1It hashes every substring of the text in advance
- ✓Correct answer: A prefix function says how far to shift without rereading text
- 3It sorts the text characters and binary searches the pattern
Explanation
For each position of the pattern, the prefix function stores the length of the longest proper prefix that's also a suffix. On a mismatch the pattern jumps by that amount, so the text pointer never moves back.