kmp_search.java

    static List<Integer> search(String pattern, String text) {
        int[] pi = buildTable(pattern);
        return kmpSearch(text, pattern, pi);
    }

    static List<Integer> kmpSearch(String text, String pattern, int[] pi) {
        List<Integer> res = new ArrayList<>();
        int p = 0;
        for (int i=0;i<text.length();i++) {
            while (p>0 && text.charAt(i) != pattern.charAt(p)) {
                p = pi[p-1];
            }
            if (text.charAt(i) == pattern.charAt(p)) {
                p++;
            }
            if (p == pattern.length()) {
                res.add(i-pattern.length()+1);
                p = pi[p]; // go back to front
            }
        }
        return res;
    }

    static int[] buildTable(String pattern) {
        int[] pi = new int[pattern.length()+1];
        int k=0;
        for (int i=2;i<pattern.length();i++) {
            char ch = pattern.charAt(i);
            while (k>0 && ch != pattern.charAt(k)) {
                k = pi[k-1];
            }
            // prefix is equal to suffix
            if (ch == pattern.charAt(k)) {
                k++;
            }
            pi[i] = k;
        }
        // uncomment the following line to enable overlap
        pi[pattern.length()] = pi[pattern.length()-1];
        return pi;
    }