CF235C Cyclical Quest解题报告

解题报告

CF235C Cyclical Quest解题报告：

更好的阅读体验

题意

题意：给定一个主串$s$和$n$个询问串$t_i$，对于每个询问串$t_i$，需要求出它所有本质不同循环同构在$s$中出现的次数之和。

数据范围：$1\leqslant|S|\leqslant 10^6$，$1\leqslant n\leqslant 10^5$，$n\leqslant \sum_{i=1}^n|t_i|\leqslant 10^6$

分析

一道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;
}