kmp模式字符串匹配算法

今天在刷算法题的过程中无意中发现了一道字符串的匹配的题目，用的是kmp算法，但是对于kmp只在考研的时候学了大概，记忆不是特别深刻，一些细节忘记了，现在重新回顾下：

由浅入深：文章建议看这一篇，很通俗易懂，能够帮你少走很多弯路。
但是这个算法的next[0]设置的是-1。看这篇文章的目的主要是明白kmp next数组的求法，递归的原因。

了解原理之后，可以看这一篇文章。next[0]设置的是0。链接

附上java代码

package KMP;

public class KMP {

    public int[] getNext(String t){
        int[] next = new int[t.length()];
        next[0] = 0;
        int i = 1, j = 0;
        while (i < t.length()) {
        	// 如果不相等，那么递归
            while (j > 0 && t.charAt(i) != t.charAt(j)){
                j = next[j];
            }
            // 如果相等，+1就够了
            if (t.charAt(i) == t.charAt(j)){
                j++;
            }
            next[i] = j;
            i++;
        }
        return next;
    }

    public int kmp(String t, String s){
        int[] next = getNext(t);
        for (int i = 0, j = 0; i < s.length(); i++){
            while (t.charAt(j) != s.charAt(i) && j > 0){
                j = next[j-1];
            }
            if (t.charAt(j) == s.charAt(i)){
                j++;
            }
            if (j == t.length()){
                System.out.println("找到了且下标为" + (i-j+1));
                return i-j+1;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        String s = "abcdabcdx";
        String t = "abcdx";
        new KMP().kmp(t, s);
    }
}

关于KPM next算法其他方面代码用一张图去代一下就好了。