题解 | #kmp算法#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    int kmp(string S, string T) {
       //求NEXT数组
        int j=0,m=S.size();
        int nextTB[S.size()+1];
	    nextTB[j]=-1;
	    int i=nextTB[j];
	    while(j<m){
		if(i==-1||  S[j]==S[i]){//初始或者当前匹配值相同 
			i++;
			j++;
			nextTB[j]=i;//nextTB[j+1]=nextTB[j]+1 
		}
		else i=nextTB[i];//不匹配则继续比较，i->next[i] ->next[next[i]],直到最终i=-1
	}
   //KMP匹配
    int n=T.size();
	int jj=0,ii=0;
	int flag=0;//统计匹配成功次数
	while(ii<n){ 
		if(jj==-1||S[jj]==T[ii]){
			ii++;
			jj++;
		}
		else jj=nextTB[jj];
		if(jj==m){
			flag++;
            jj=nextTB[jj];//允许重复匹配
        
		}
		
	}
   return flag;
    }

};