KMP

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

package KMP; public class Main { public static void main(String[] args) { System.out.println("KMP"); KMP kmp = new KMP("THIS IS A TEST TEXT", "TEST"); kmp.search(); KMP kmp1 = new KMP("AABAACAADAABAABA", "AABA"); kmp1.search(); } } class KMP{ String texts = ""; String pattern = ""; int nt, np; int[] lps; KMP(String t, String p){ texts = t; pattern = p; nt = texts.length(); np = pattern.length(); lps = new int[np]; } void preProcess(){ for(int i=1; i<np; ++i){ int l = lps[i-1]; while(l>0 && pattern.charAt(i)!=pattern.charAt(l)){ l = lps[l-1]; } if(pattern.charAt(l)==pattern.charAt(i)){ lps[i] = l+1; } } } void search(){ preProcess(); int i = 0, j = 0; while(i<nt && j<np){ if(texts.charAt(i)!=pattern.charAt(j)){ i++; j = lps[j]; }else{ if(j==np-1){ System.out.println(i+1-np); i++; j = lps[j]; }else{ i++; j++; } } } } }