my

[[SAM]]
link

他想问"有多少(s)的子串与给定的字符串(x)循环同构"
给定字符串(s)和n个字符串(x_i)，对于每个字符串(x_i)找到，(s)中有多少连续的子字符串与(x_i)循环同构。

%%> So he wants to ask "how many consecutive substrings of (s) are cyclical isomorphic to a given string (x)". You are given string (s) and (n) strings (x_i), for each string (x_i) find, how many consecutive substrings of (s) are cyclical isomorphic to (x_i).
%%

因为学过了SAM，所以这题能直接看出要用SAM

Sol

首先，考虑一个更简单的问题
%%First, consider an easier problem.%%

[!question] 字符串(s)中，(x) 出现了多少次
%%>[!question] How many times does a string (x) occur in a string (s) ?%%

这是一个SAM的典型应用
%%It's a typical application of SAM.%%

我们要做的就是，在(s)上建一个SAM，然后上传每个状态的出现次数（用topo或者dfs）
%%What we need to do is just build a SAM on string (s), then update the times every state occurs (by topo or dfs).%%

然后，读入询问字符串(x)，遍历(x)，通过ch在SAM上walk
%%Then, we can read the query string (x). Walk in the automaton by ch while iterating (x).%%

找到包含(x)的最后一个状态，输出这个状态的出现次数（它的儿子的出现次数已经上传上来了）
%%Find the latest state included (x). Finally, print the times of this state.%%

[!question] 那么有多少(s)的子串与给定的字符串(x)循环同构 怎么求呢？
%%>[!question] How many consecutive substrings of (s) are cyclical isomorphic to a given string (x) ?%%

显然，复杂度是一样的，我们依旧是要(O(n))解决
%%Obviously, the complexity is the same. We should do operations in linear time.%%

在最右侧加，在最左侧删
%%> ADD to the rightmost and DELETE the leftmost.%%

我们可以用ch走过去，还能用fa走回来
（ch实现右加，fa实现左删）
%%We can walk forwards by ch and walk backwards by fa.%%

如果前面没路了，我们可以稍退一步，也就是删一个最左边的字符
（加和删都是对当前匹配的字符串的"操作"）
%%If we have no way forwards, we turn back to find ways.
If we do that, the leftmost characters will be deleted.%%

如果当前字符串的状态的长度到了(|x|)，就必须删左边（为了继续向右走）
%%If the length of current state reaches (|x|), we must delete the leftmost character(this operation might make you walk back).%%

另外，每个可能的x只能被记一次
%%In addition, the times of every passible kinds of (x) can only be added once.%%

#include<bits/stdc++.h>
#define l(x) _[x].len
#define chp _[p].ch[c]
#define fa(x) _[x].fa
using namespace std;
const int N=2000006;
int t,n,p,np,la=1,q,nq,T=1,sz[N],l,ans,vis[N];
char s[N];
struct A{int fa,ch[26],len;}_[N];
void add(int c){
	for(p=la,la=np=++T,sz[np]=1,l(np)=l(p)+1;p&&!chp;p=fa(p))chp=np;
	if(!p){fa(np)=1;return;}if(l(q=chp)==l(p)+1){fa(np)=q;return;}
	for(nq=++T,_[nq]=_[q],l(nq)=l(p)+1,fa(np)=fa(q)=nq;p&&chp==q;p=fa(p))chp=nq;
}
vector<int>e[N];
void dfs(int u){for(int x:e[u])dfs(x),sz[u]+=sz[x];}
int main(){
	int i,j;
	for(i=0,cin>>s;s[i];i++)add(s[i]-'a');
	for(i=1;i<=T;i++)e[fa(i)].push_back(i);dfs(1);
	for(cin>>t,t++;--t;){
		cin>>s;n=strlen(s);strcpy(s+n,s);
		for(ans=l=i=0,p=1;s[i];i++){
			for(;p&&!_[p].ch[s[i]-'a'];)l=l(p=fa(p));
			if(!p){puts("0");goto E;}
			l++,p=_[p].ch[s[i]-'a'];
			l==n&&(vis[p]!=t&&(vis[p]=t,ans+=sz[p]),--l==l(fa(p))&&(p=fa(p)));
		}
		printf("%dn",ans);E:;
	}
}
/*use topo
int deg[N],r,que[N],o;
void get_size(){
	for(int i=1;i<=tot;i++)deg[fa(i)]++;
	for(int i=1;i<=tot;i++)if(!deg[i])que[r++]=i;
	for(;l<=r;l++){
		o=que[l];
		sz[fa(o)]+=sz[o];
		if(!--deg[fa(o)])que[r++]=fa(o);
	}
}*/

This is the shortest solution code in CF.