Which string-matching algorithm uses a 'prefix function' (or failure function) to avoid redundant comparisons?
Show answer
Knuth-Morris-Pratt (KMP)
The KMP algorithm achieves O(n + m) time by pre-processing the pattern to find the longest proper prefix that is also a suffix, allowing the search to skip over characters that have already been matched.
Also asked as:
- Which string-matching algorithm avoids redundant character comparisons by using a 'prefix function' to pre-process the pattern?