传送门

写的时候挺蛋疼的。

刚开始的时候思路没跑偏，无非就是建个SAM然后把串开两倍然后在SAM上跑完后统计贡献。但是卡在第二个样例上就是没考虑相同的情况。

然后开始乱搞，发现会出现相同串的只有可能是由一个串无限拼接构成的串，于是上了个KMP来搞循环串..然后就没有然后了

基本上一直处于改了这个错误后又被另一个错误卡着的状态，后来没办法了，翻题解..

然后发现只需要在SAM的节点上开个标记就行了...

越学越傻啊...

至于为什么KMP会挂掉..求dalao评论指出

//Codeforces 235C//by Cydiater//2017.1.22#include <iostream>#include <queue>#include <map>#include <iomanip>#include <cstring>#include <string>#include <cstdlib>#include <cstdio>#include <algorithm>#include <cmath>#include <ctime>#include <bitset>#include <set>#include <vector>using namespace std;#define ll long long#define up(i,j,n)	for(int i=j;i<=n;i++)#define down(i,j,n)	for(int i=j;i>=n;i--)#define cmax(a,b)	a=max(a,b)#define cmin(a,b)	a=min(a,b)const int MAXN=2e6+5;const int oo=0x3f3f3f3f;int rnk[MAXN],N,Right[MAXN],M,len,ans,flag[MAXN];char s[MAXN];struct SAM{	int now,cnt,son[MAXN][26],step[MAXN],pre[MAXN],label[MAXN];	SAM(){now=cnt=1;}	void Extend(int nxt){		int p=now,np=++cnt;now=np;		step[np]=step[p]+1;Right[np]=1;		for(;(!son[p][nxt])&&p;p=pre[p])son[p][nxt]=np;		if(!p)pre[np]=1;		else{			int q=son[p][nxt],nq;			if(step[q]==step[p]+1)pre[np]=q;			else{				step[(nq=++cnt)]=step[p]+1;				memcpy(son[nq],son[q],sizeof(son[q]));				pre[nq]=pre[q];				pre[np]=pre[q]=nq;				for(;son[p][nxt]==q;p=pre[p])son[p][nxt]=nq;			}		}	}	void Toposort(){		up(i,1,cnt)label[step[i]]++;		up(i,1,N)label[i]+=label[i-1];		up(i,1,cnt)rnk[label[step[i]]--]=i;		down(i,cnt,1){			int node=rnk[i];			Right[pre[node]]+=Right[node];		}	}	void Go(){		now=1;int Len=0;		up(i,1,(len<<1)-1){			int nxt=s[i]-‘a‘;			for(;now&&(!son[now][nxt]);now=pre[now],Len=step[now]);			if(!now){now=1;Len=0;}			if(son[now][nxt]){now=son[now][nxt];Len++;}			for(;now&&step[pre[now]]>=len;now=pre[now],Len=step[now]);			if(step[pre[now]]<len&&step[now]>=len&&Len>=len){				if(flag[now]!=M+1){					ans+=Right[now];					flag[now]=M+1;				}			}		}	}}sam;namespace solution{	void Prepare(){		scanf("%s",s+1);		N=strlen(s+1);		up(i,1,N)sam.Extend(s[i]-‘a‘);		sam.Toposort();	}	void Solve(){		cin>>M;		while(M--){			scanf("%s",s+1);			len=strlen(s+1);			up(i,1,len-1)s[i+len]=s[i];			ans=0;			sam.Go();			printf("%d\n",ans);		}	}}int main(){	//freopen("input.in","r",stdin);	using namespace solution;	Prepare();	Solve();	return 0;}

Codeforces 235C. Cyclical Quest