# kmp算法笔记

// s为主串,i为主串指针，t为模式串，j为模式串指针
int kmp(String s,String t){
    int[] next = getNext(t);
    int j = 0;
    for(int i = 0;i <s.length();i++){
        while(j > 0 && s.charAt(i) != t.charAt(j)){
            j = next[j-1];
        }
        if(s.charAt(i) == t.charAt(j)){
            j++;
        }
        if(j == t.length()){
            return i-j+1;
            // j =next[j-1];  //  如果要求模式串在主串中所有位置，那么在这一步可以继续将j回溯
        }
    }
    return -1;   //如果不匹配返回-1
}


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