kmp算法 Java

public class KmpTest {
    public static void main(String[] args) {
        System.out.println(new KmpSulution().strStr("abababababc", "ababc"));

        System.out.println(new KmpSulution().strStr("abcabcabcd", "abcde"));
    }

    public int strStr(String haystack, String needle) {
        int i = 0;
        int j = 0;
        int[] next = getNext(needle);
        while (i < haystack.length() && j < needle.length()) {
            if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == needle.length()) {
            return i - j;
        } else {
            return -1;
        }
    }

    public int[] getNext(String sub) {
        int[] next = new int[sub.length() + 1];
        int i = 0;
        int j = -1;
        while (i < sub.length()) {
            if (j == -1 || sub.charAt(i) == sub.charAt(j)) {
                next[++i] = ++j;
            } else {
                j = next[j];
            }
        }
        return next;
    }
}
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