Spoj SUBST1 New Distinct Substrings

Given a string, we need to find the total number of its distinct substrings.

Input

T- number of test cases. T<=20; Each test case consists of one string, whose length is <= 50000

Output

For each test case output one number saying the number of distinct substrings.

Example

Input:

2

CCCCC

ABABA

Output:

5

9

就是让你求一下一个串的本质不同的子串的个数。
这个就等价于求一下后缀自动机每个节点的权值和，每个节点的权值等于(max{}-min{}+1)

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<cstring>

#define ll long long

using namespace std;

#define maxn 200005

int f[maxn],ch[maxn][26],cnt=1;

int n,siz[maxn],l[maxn],T,las=1;

int a[maxn],c[maxn];

char s[maxn];

ll ans=0;

inline void init(){

	cnt=las=1;

	memset(f,0,sizeof(f));

	memset(ch,0,sizeof(ch));

	memset(c,0,sizeof(c));

	siz[1]=l[1]=ans=0;

}

inline void ins(int x){

	int p=las,np=++cnt;

	las=np,l[np]=l[p]+1;

	siz[np]=1;

	for(;p&&!ch[p][x];p=f[p]) ch[p][x]=np;

	if(!p) f[np]=1;

	else{

		int q=ch[p][x];

		if(l[q]==l[p]+1) f[np]=q;

		else{

			int nq=++cnt;

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

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

			f[nq]=f[q];

			f[q]=f[np]=nq;

			for(;ch[p][x]==q;p=f[p]) ch[p][x]=nq;

		}

	}

}

inline void build(){

	for(int i=0;i<n;i++) ins(s[i]-'a');

}

inline void solve(){

	for(int i=1;i<=cnt;i++) ans+=(ll)(l[i]-l[f[i]]);

}

int main(){

	scanf("%d",&T);

	while(T--){

		init();

		scanf("%s",s);

		n=strlen(s);

		build();

		solve();

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

	}

	return 0;

}

巴特西

Spoj SUBST1 New Distinct Substrings

Input

Output

Example

最新文章

热门文章