Knuth-Morris-Pratt method of string matching

 Public void KMP-Matcher(String text, String pattern) { 

Int n = text.length(); 

Int m = pattern.length(); 

Int[] prefixes = ComputePrefixFunction(pattern); 

Int noOfCharMatched = 0; 

for ( int I = 1; I <= n; I++) { 

       While (noOfCharMatched > 0 && pattern[noOfCharMatched + 1] != Text[I]) 

    NoOfCharMatched = prefixes[nofOfCharMatched] 

       If (pattern[noOfCharMatched + 1] == text[I])  

   NoOfCharMatched = NoOfCharMatched + 1; 

       If (noOfCharMatched == m) { 

                 System.out.println(“Pattern occurs at “ + I); 

                 NoOfCharMatched = prefixes[NoOfCharMatched]; 

        } 

} 

} 

Public int[] ComputePrefixFunction(String pattern) { 

Int m = pattern.length(); 

Int[] prefixes  = new int[m+1]; 

Prefixes[1] = 0; 

Int k = 0; 

For (int q = 2; q <=m ; q++) { 

While (k > 0 && Pattern[k + 1] != Pattern[q]) 

       K = pattern[k]; 

If (pattern[k+1] == Pattern[q]) { 

      K = k + 1; 

} 

Pattern[q] = k; 

} 

Return prefixes; 

}