HDU 6629 (2019杭电第五场 1006) string matching (扩展kmp)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int K=1000005;
int nt[K],extand[K];
char S[K],T[K];
int a[K];
ll ans;
void Getnext(char *T,int *next)
{
    int len=strlen(T),a=0;
    next[0]=len;
    while(a<len-1 && T[a]==T[a+1]) a++;
    next[1]=a;
    a=1;
    for(int k=2; k<len; k++)
    {
        int p=a+next[a]-1,L=next[k-a];
        if( (k-1)+L >= p)
        {
            int j = (p-k+1)>0 ? (p-k+1) : 0;
            while(k+j<len && T[k+j]==T[j]) j++;
            next[k]=j;
            a=k;
        }
        else
            next[k]=L;
    }
}
void GetExtand(char *S,char *T,int *next)
{
    Getnext(T,next);
    int slen=strlen(S),tlen=strlen(T),a=0;
    int MinLen = slen < tlen ? slen : tlen;
    while(a<MinLen && S[a]==T[a]) a++;
    extand[0]=a;
    a=0;
    for(int k=1; k<slen; k++)
    {
        int p=a+extand[a]-1, L=next[k-a];
        if( (k-1)+L >= p)
        {
            int j= (p-k+1) > 0 ? (p-k+1) : 0;
            while(k+j<slen && j<tlen && S[k+j]==T[j]) j++;
            extand[k]=j;
            a=k;
        }
        else
            extand[k]=L;
    }
}
//以上是模版
int main(void)
{
	int tl;scanf("%lld",&tl);
    while(tl--)
    {
    	memset(nt,0,sizeof(nt));
    	memset(extand,0,sizeof(extand));
    	memset(a,0,sizeof(a));
		scanf("%s",S);
    	ans = 0;
    	strcpy(T,S);
        GetExtand(S,T,nt);
        int len = strlen(T);
        queue<int> id;
		ans = 0;
		ans+=len-1;
		for(int i=1; i<len; i++) {
			if(nt[i]!=0) {
				ans+=nt[i];
				if(i+nt[i]>=len)ans--;
			}
		}
		printf("%lld\n",ans);
    }
    return 0;
}
/*
3
_Happy_New_Year_
ywwyww
zjczzzjczjczzzjc

17
7
32
*/