Thursday, August 8, 2024

 This is the 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; 


}


Reference: for drone data: https://1drv.ms/w/s!Ashlm-Nw-wnWhPFoQ0k-mnjii2Gs3Q?e=cbET9N 


No comments:

Post a Comment