利用java实现简单的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
public static int kmp(String str, String pattern){
   int i = 0;
   int j = 0;
   int [] next = calcNextArr(pattern);

   while(i < str.length()){
      if(str.charAt(i) == pattern.charAt(j)){
         i++;
         j++;
      } else if(j > 0){
         j = next[j-1];
      } else {
         i++;
      }
      if (j == pattern.length()) {
         return i - j;
      }
   }
   return -1;
}

public static int[] calcNextArr(String pattern){
   int len = pattern.length();
   int [] next = new int[len];
   int i = 0;
   int j = 1;
   while(j < len){
      if(pattern.charAt(i)==pattern.charAt(j)){
         next[j++] = ++i;
      }else if (i > 0){
         i = next[i-1];
      }else{
         next[j++] = i;
      }
   }
   return next;
}