题解 | #kmp算法#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 计算模板串S在文本串T中出现了多少次
 * @param S string字符串 模板串
 * @param T string字符串 文本串
 * @return int整型
 */
//求模板串的next数组,注意S和T字符串，下标从0开始算起，所以与王道书籍的代码相比有所改动。
void GetNext(char S[],int next[]){
    next[1]=0;
    int i=1,j=0;
    while(i<=strlen(S)){
        if(j==0||S[i-1]==S[j-1]){
            i++;j++;
            next[i]=j;
        }
        else j=next[j];  
    }
}

int kmp(char* S, char* T ) {
    int a=strlen(S),num=0;
    int next[a+2];
    GetNext(S,next);
    for(int i=0,j=0;i<strlen(T);){
        if(S[j]==T[i]){
            i++;j++;
            if(j==strlen(S)){
                num++;
                j=next[j+1]-1;                
            }
        }
        else{
            if(j==0) i++;
            else j=next[j+1]-1;;
        }         
    }
    return num;
}