大学被虐了很久的kmp算法

关键在于实现最长公共前后缀table。一个字符串的最长公共前后缀举例：比如"abcdabc"的最长公共前后缀为“abc”, "aaaa"的最长公共前后缀为“aaa”(不包括自己)。

private boolean kmp(String target, String pattern) {
        int m = target.length(), n = pattern.length();
        int i = 0, j = 0;
        int[] prefixTable = getPrefixTable(pattern);
        while (i < m && j < n) {
            if (target.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else if (j == 0) {
                i++;
            } else {
                j = prefixTable[j-1];
            }
        }
        return j == n;
    }

    private int[] getPrefixTable(String pattern) {
        int n = pattern.length();
        int[] prefix = new int[n];
        prefix[0] = 0;
        for (int i=1; i<n; i++) {
            int len = prefix[i-1];
            while (pattern.charAt(len) != pattern.charAt(i)) {
                if (len == 0) {
                    len--; break;
                }
                len = prefix[len-1];
            }
            prefix[i] = len + 1;
        }
        return prefix;
    }