【SPOJ】Distinct Substrings

求不同子串数量

统计每个点有效的字符串数量（第一次出现的）

\(\sum\limits_{now=1}^{nod}now.longest-parents.longest\)

My complete code

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL maxn=3000;

LL nod,last,n,T;

LL len[maxn],fail[maxn],son[maxn][26];

char s[maxn];

inline void Insert(LL c){

	LL np=++nod,p=last;

	len[np]=len[p]+1;

	last=np;

	while(p&&!son[p][c]){

		son[p][c]=np,

		p=fail[p];

	}

	if(!p)

	    fail[np]=1;

	else{

		LL q=son[p][c];

		if(len[q]==len[p]+1)

		    fail[np]=q;

		else{

			LL nq=++nod;

			len[nq]=len[p]+1;

			fail[nq]=fail[q];

			memcpy(son[nq],son[q],sizeof(son[q]));

			fail[np]=fail[q]=nq;

			while(p&&son[p][c]==q){

				son[p][c]=nq,

				p=fail[p];

			}

		}

	}

}

int main(){

	scanf("%lld",&T);

	while(T--){

		memset(son,0,sizeof(son));

		nod=last=1;

		scanf(" %s",s);

		for(LL i=0;i<strlen(s);++i)

		    Insert(s[i]-'A');

		LL ans=0;

		for(LL i=1;i<=nod;++i)

		    ans+=len[i]-len[fail[i]];

		printf("%lld\n",ans);

	}

	return 0;

}

巴特西

【SPOJ】Distinct Substrings

My complete code

最新文章

热门文章