KMP算法

KMP算法指的是字符串模式匹配算法，问题是：在主串T中找到第一次出现完整子串P时的起始位置。

kpm算法看了几天勉强看懂，但是过了几天就完全忘了当时怎么想的，所以直接背吧！

class Kmp{
    public int findSubString(String t,String p){
        int[] next = getNext(p);
        for(int i = 0, j = 0; i < t.length();i++){
            while(j > 0 && p.charAt(i) != p.charAt(j)) j = next[j - 1];
            if(p.charAt(i) == p.charAt(j)) j++;
            if(j == p.length()) return i - j + 1;
        }
        return -1;
    }
    public int[] getNext(String p){
        int[] next = new int[p.length()];
        next[0] = 0;
        for(int i = 1,j = 0; i < p.length();i++){
            while(j > 0 && p.charAt(i) != p.charAt(j)) j = next[j - 1];
            if(p.charAt(i) == p.charAt(j)) j++;
            next[i] = j;
        }
        return next;
    }
}