KMP算法

 1 public class Main {
 2 
 3     public static void main(String[] args) {
 4         String s = "abcabcababaccc";
 5         String m = "ab";
 6         
 7         System.out.println(getIndex(s, m));
 8     }
 9 
10     public static int getIndex(String s, String m) {
11         if(s.length() < m.length()) {
12             return -1;
13         }
14 
15         char[] str1 = s.toCharArray();
16         char[] str2 = m.toCharArray();
17         
18         int i1 = 0;
19         int i2 = 0;
20 
21         int[] next = getNextArray(str2);
22 
23         while(i1 < str1.length && i2 < str2.length) {
24             if(str1[i1] == str2[i2]) {
25                 i1++;
26                 i2++;
27             } else if(next[i2] == -1) {
28                 i1++;
29             } else {
30                 i2 = next[i2];
31             }
32         }
33 
34         return i2 == str2.length?i1-i2:-1;
35     }
36 
37     public static int[] getNextArray(char[] str) {
38         if(str.length == 1) {
39             return new int[]{-1};
40         }
41 
42         int[] next = new int[str.length];
43         next[0] = -1;
44         next[1] = 0;
45 
46         int i = 2;
47         int cn = 0;
48 
49         while(i < next.length) {
50             if(str[i-1] == str[cn]) {
51                 next[i++] = ++cn;
52             } else if(cn > 0) {
53                 cn = next[cn];
54             } else {
55                 next[i++] = 0;
56             }
57         }
58 
59         return next;
60     }
61 }