Codeforces 235C Cyclical Quest (后缀自动机)

题目链接: https://codeforces.com/contest/235/problem/C

题解:

对大串建后缀自动机

对询问串复制拆环。这里一定要注意是复制一个循环节不是复制整个串！循环节是要整除的那种

然后要做的实际上是在大串上跑，每经过一个点求出当前的最长公共子串，如果大于等于(n)的话，则向上跳Parent树找到(nin [minlen[v],maxlen[v]])的那个祖先(v)

这玩意直接做复杂度是错的(虽然貌似网上有直接做过了的)，但是我们可以递推！

考虑递推，实际上就是维护一个长度为(m)(询问串长度)的队列，每次删掉第一个字符(就是判断如果当前最长公共子串长(=n)就变成(n-1), 如果需要的话跳到父亲)，然后每次长度达到(n)时(ans+=len[u])即可。

代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

const int N = 1e6;
const int S = 26;
char a[N+3];
char b[(N<<1)+3];
int son[(N<<1)+3][S+3];
int fa[(N<<1)+3];
int len[(N<<1)+3];
int vis[(N<<1)+3];
int ord[(N<<1)+3];
int buc[N+3];
int nxt[N+3];
int sz[(N<<1)+3];
int n,q,m,siz,rtn,lstpos;

void initSAM()
{
	siz = rtn = lstpos = 1;
}

void KMP()
{
	nxt[0] = nxt[1] = 0;
	for(int i=2; i<=m; i++)
	{
		nxt[i] = nxt[i-1];
		while(nxt[i] && b[nxt[i]+1]!=b[i])
		{
			nxt[i] = nxt[nxt[i]];
		}
		if(b[nxt[i]+1]==b[i]) nxt[i]++;
	}
}

void insertchar(char ch)
{
	int p = lstpos,np; siz++; np = lstpos = siz; len[np] = len[p]+1; sz[np]++;
	for(; p && son[p][ch]==0; p=fa[p]) {son[p][ch] = np;}
	if(p==0) {fa[np] = rtn;}
	else
	{
		int q = son[p][ch];
		if(len[q]==len[p]+1) {fa[np] = q;}
		else
		{
			siz++; int nq = siz; len[nq] = len[p]+1;
			memcpy(son[nq],son[q],sizeof(son[q]));
			fa[nq] = fa[q]; fa[q] = fa[np] = nq;
			for(; p && son[p][ch]==q; p=fa[p]) {son[p][ch] = nq;}
		}
	}
}

int main()
{
	initSAM();
	scanf("%s",a+1); n = strlen(a+1);
	for(int i=1; i<=n; i++) a[i]-=96;
	for(int i=1; i<=n; i++) {insertchar(a[i]);}
	for(int i=1; i<=siz; i++) buc[len[i]]++;
	for(int i=1; i<=n; i++) buc[i] += buc[i-1];
	for(int i=siz; i>=1; i--) ord[buc[len[i]]--] = i;
	for(int i=siz; i>=1; i--)
	{
		int u = ord[i];
		sz[fa[u]] += sz[u];
	}
	scanf("%d",&q);
	while(q--)
	{
		scanf("%s",b+1); m = strlen(b+1);
		for(int i=1; i<=m; i++) b[i]-=96;
		KMP();
		int cyclen = nxt[m];
		while(cyclen>0 && m%(m-cyclen)!=0)
		{
			cyclen = nxt[cyclen];
		}
		cyclen = m-cyclen;
		for(int i=1; i<cyclen; i++) b[i+m] = b[i];
		int u = rtn,cur = 0,ans = 0;
		for(int i=1; i<m+cyclen; i++)
		{
			while(u && son[u][b[i]]==0) {u = fa[u]; cur = len[u];}
			if(son[u][b[i]]!=0) {u = son[u][b[i]]; cur++;}
			else {u = rtn; cur = 0;}
			if(cur==m)
			{
				ans += sz[u];
				cur--;
				if(cur<=len[fa[u]])
				{
					u = fa[u];
				}
			}
		}
		printf("%d
",ans);
	}
	return 0;
}