KMP模板

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
using namespace std;

const int N = 1000002;
int nextt[N];
int ex[N];
char S[N],T[N];
//vector<int>S,T;
int slen, tlen;

void getNext()
{
    int j, k;
    j = 0; k = -1; nextt[0] = -1;
    while(j < tlen)
        if(k == -1 || T[j] == T[k])
            nextt[++j] = ++k;
        else
            k = nextt[k];

}
/*
返回模式串T在主串S中首次出现的位置
返回的位置是从0开始的。
*/
char s1[N],s2[N];
void EXKMP()
{
    int i = 0, j, po, len = strlen(s1), l2 = strlen(s2);
    getNext();//计算子串的next数组，先改动T为s1，tlen为strlen(s1);
    while(s1[i] == s2[i] && i < l2 && i < len) //计算ex[0]
        i++;
    ex[0] = i;
    po = 0; //初始化po的位置
    for(i = 1; i < len; i++)
    {
        if(nextt[i - po] + i < ex[po] + po) //第一种情况，直接可以得到ex[i]的值
            ex[i] = nextt[i - po];
        else//第二种情况，要继续匹配才能得到ex[i]的值
        {
            j = ex[po] + po - i;
            if(j < 0)j = 0; //如果i>ex[po]+po则要从头开始匹配
            while(i + j < len && j < l2 && s1[j + i] == s2[j]) //计算ex[i]
                j++;
            ex[i] = j;
            po = i; //更新po的位置
        }
    }
}
int KMP_Index(){//拓展KMP，求s1以i开始的后缀串与s2的最长前缀串长度
	int i = 0, j = 0,ans=0;//ans=-1;//只计算一次位置时调用
	getNext();
	while(i < slen){ 
		if(j == -1 || S[i] == T[j]){ 
			i++; j++;
		}else 
			j = nextt[j]; 
		if(j == tlen){ 
			//ans++,j=0;//语句1 
			//ans++,j=nextt[j];//语句2 
			//ans=i-j+1;break;//语句3 
		} 
	}
	return ans; 
}

int main()
{
    
    int TT;
    int i, cc;
    while(1)
    {
    	scanf("%s", S);
    	scanf("%s", T);
        slen = strlen(S);
        tlen = strlen(T);
        cout<<KMP_Index()<<endl;
    }