• 欢迎光临~

# my

[[SAM]]

%%> 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).
%%

## Sol

%%First, consider an easier problem.%%

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

%%It's a typical application of SAM.%%

%%What we need to do is just build a SAM on string (s), then update the times every state occurs (by topo or dfs).%%

%%Then, we can read the query string (x). Walk in the automaton by `ch` while iterating (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) ?%%

%%Obviously, the complexity is the same. We should do operations in linear time.%%

%%> ADD to the rightmost and DELETE the leftmost.%%

`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.%%

%%If the length of current state reaches (|x|), we must delete the leftmost character(this operation might make you walk back).%%

%%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];
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=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.