KMP

学习自：http://www.cnblogs.com/SYCstudio/p/7194315.html
我的实现

    public final static List<Integer> KMP(String a, String b) {
        List<Integer> res = new ArrayList<>();
        int[] next = new int[b.length()];
        next[0] = -1;
        for(int i = 1; i < next.length; ++i) {
            int j = next[i-1];
            while(b.charAt(i) != b.charAt(j + 1) && j >= 0) 
                j = next[j];
            if(b.charAt(i) == b.charAt(j + 1)) {
                next[i] = j + 1;
            }
            else {
                next[i] = -1;
            }
        }
        int i = 0;
        int j = 0;
        while(i < a.length()) {
            if(a.charAt(i) == b.charAt(j)) {
                i++;
                j++;
                if(j == b.length() - 1) {
                    res.add(i - b.length() + 1);
                    j = next[j - 1] + 1;
                }
            }
            else {
                if(j == 0) 
                    i++;
                else 
                    j = next[j - 1] + 1;
                
            }
        }
        return res;
    }