题解 CF235C 【Cyclical Quest】

· · 题解

分析

一道SAM好题，考察了对DAWG和Parent Tree的理解。

解释循环同构的定义：给定字符串 s_1\cdots s_n （每个 s 是字符），它的循环同构为： s_1\cdots s_n ， s_2\cdots s_ns_1 ， s_3\cdots s_n s_1 s_2 ， \cdots ， s_ns_1\cdots s_{n-1} （比如说， aab 的循环同构有 aab ， baa ， aba ）。

考虑循环同构的实质，其实是在前面去除一个字符，并在后面添加一个字符。

在前面去除一个字符？根据endpos和后缀link的性质，一个属于状态 s 的串在前面去除一个字符要么还在这个状态 s ，要么跳后缀link到 link_s 。

在后面添加一个字符？根据DAWG边的定义（其实就是后缀自动机里的边），一个属于状态 s 的串在后面添加字符 x 会跳转到状态 nxt_{s,x} 。

这就比较好办了，我们输入 t 后复制一遍它放在它后面（注意不要复制最后一个字符），这样形成的 t' 就会包含 t 的所有循环同构。

然后循环每个字符进行匹配，按照上面的方式跳后缀link和DAWG边，并维护长度 l ，如果长度 l=|t| 就记录答案（ l=|t| 意味着整个子串都成功匹配），注意记录完答案后需要强制失配，这样就不会让长度 l>|t| 了。

因为 t 的所有循环同构长度都等于 |t| ，所以如果 l>|t| 一定是倍长 t 的锅，比如 s=aaaaa ， t=aa ，倍长后 t'=aaaa ，这会让匹配的长度大于 |t| 。

至于本质不同，其实很好处理。我们在每一次记录答案的时候可以作一个标记（我使用的是时间戳标记，这样不需要给数组清空），标记后的结点不对答案做贡献就可以了。

代码

#include<stdio.h>
const int maxn=2000005,maxk=30,maxm=2000005,maxt=2000005;
int i,j,k,m,n,T,tot,last,e,stp,cnt;
int len[maxn],link[maxn],nxt[maxn][maxk],start[maxn],to[maxm],then[maxm],tag[maxn],size[maxn],vis[maxn],s[maxn],t[maxn];
char c;
inline void add(int x,int y){
    then[++e]=start[x],start[x]=e,to[e]=y;
}
int extend(int last,int x){
    int pos=last,now=++tot,tmp,cln;
    tag[now]=1;
    len[now]=len[pos]+1;
    while(pos!=0&&nxt[pos][x]==0)
        nxt[pos][x]=now,pos=link[pos];
    if(pos==0){
        link[now]=1;
        return now;
    }
    tmp=nxt[pos][x];
    if(len[tmp]==len[pos]+1){
        link[now]=tmp;
        return now;
    }
    cln=++tot;
    len[cln]=len[pos]+1;
    for(int i=1;i<=26;i++)
        nxt[cln][i]=nxt[tmp][i];
    link[cln]=link[tmp],link[tmp]=link[now]=cln;
    while(pos!=0&&nxt[pos][x]==tmp)
        nxt[pos][x]=cln,pos=link[pos];
    return now;
}
void dfs(int x){
    size[x]=tag[x];
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        dfs(y);
        size[x]+=size[y];
    }
}
int main(){
    for(c=getchar();c<'a'||c>'z';c=getchar());
    for(;c>='a'&&c<='z';c=getchar())
        s[++cnt]=c-96;
    last=tot=1;
    for(i=1;i<=cnt;i++)
        last=extend(last,s[i]);
    for(i=2;i<=tot;i++)
        add(link[i],i);
    dfs(1);
    scanf("%d",&T);
    while(T--){
        int now=1,l=0,ans=0;
        cnt=0,stp++;
        for(c=getchar();c<'a'||c>'z';c=getchar());
        for(;c>='a'&&c<='z';c=getchar())
            t[++cnt]=c-96;
        for(i=cnt+1;i<2*cnt;i++)
            t[i]=t[i-cnt]; 
        for(i=1;i<2*cnt;i++){
            while(now!=0&&nxt[now][t[i]]==0)
                now=link[now],l=len[now];
            if(nxt[now][t[i]])
                l++,now=nxt[now][t[i]];
            else l=0,now=1;
            if(l==cnt){
                if(vis[now]!=stp)
                    vis[now]=stp,ans+=size[now];
                if(len[link[now]]+1==cnt)
                    now=link[now];
                l--;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}