Problem Statement
What is the main advantage of the KMP algorithm over the naive pattern matching approach?
Explanation
The Knuth-Morris-Pratt algorithm preprocesses the pattern to create a longest prefix-suffix table, allowing it to skip characters that have already been matched. This reduces the time complexity to O(n+m).
Code Solution
SolutionRead Only
void computeLPS(String pat,int[] lps){
int len=0; lps[0]=0; int i=1;
while(i<pat.length()){
if(pat.charAt(i)==pat.charAt(len)) lps[i++]=++len;
else if(len!=0) len=lps[len-1];
else lps[i++]=0; }
}
// KMP avoids backtracking text index.Practice Sets
This question appears in the following practice sets:
