hiho# 1465 重复旋律8 循环串计数后缀自动机

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目传送门

题意：给出一个母串，再给出n个串，问对于每个串，母串中有几个子串是可以通过循环变化得到这个串。

思路：对母串建SAM，求出$right$集。

把匹配串复制一遍，和母串进行匹配，当匹配长度大于等于$siz$时，将当时的$p$跳到最远的$len$还大于$siz$的父串（不停的往父亲跳），答案加上$right$，然后标记一下，如果标记过的就不加。（因为此时这个p是唯一的，不会被重复计算）

#include<bits/stdc++.h>

#define clr(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

const ll mod=1e9+;

const int maxn=;

char s[maxn];

int len[maxn<<],ch[maxn<<][],fa[maxn<<],tot=,root=,last=,siz,r[maxn<<],vis[maxn<<];

int a[maxn<<],c[maxn<<],ans[maxn<<];

ll dp[maxn<<];

void extend(int x){

    int now=++tot,pre=last;

    r[now]=;

    last=now,len[now]=len[pre]+;

    while( pre && !ch[pre][x]){

        ch[pre][x]=now;

        pre=fa[pre];

    }

    if(!pre)fa[now]=root;

    else{

        int q = ch[pre][x];

        if(len[q]==len[pre]+)fa[now]=q;

        else {

            int nows=++tot;

            memcpy(ch[nows],ch[q],sizeof(ch[q]));

            len[nows]=len[pre]+;

            fa[nows]=fa[q];

            fa[q]=fa[now]=nows;

            while(pre&&ch[pre][x]==q){

                ch[pre][x]=nows;

                pre=fa[pre];

            }

        }

    }

}

void topSort(){

    for(int i=;i<=tot;i++)c[len[i]]++;

    for(int i=;i<=tot;i++)c[i]+=c[i-];

    for(int i=tot;i>;i--)a[c[len[i]]--]=i;

    for(int i=tot;i>;i--)r[fa[a[i]]]+=r[a[i]];

}

int cal(int p,int inx){

    while(fa[p]&&len[fa[p]]>=siz)p=fa[p];

    return vis[p]==inx?:(vis[p]=inx,r[p]);

}

int main(){

    scanf("%s",s);

    siz=strlen(s);

    for(int i=;i<siz;i++){

        int p=s[i]-'a';

        extend(p);

    }

    topSort();

    int n;

    cin>>n;

    int index=;

    while(n--){

        scanf("%s",s);

        siz=strlen(s);

        for(int i=;i<siz;i++)

        {

            s[i+siz]=s[i];

        }

        int cur=,maxx=;

        ll ans=;

        for(int i=;i<(siz<<);i++)

        {

            int p=s[i]-'a';

            if(ch[cur][p]){

                maxx++;

                cur=ch[cur][p];

            }else{

                while(cur&&ch[cur][p]==)cur=fa[cur];

                if(cur){

                    maxx=len[cur]+;

                    cur=ch[cur][p];

                }else{

                    maxx=;

                    cur=;

                }

            }

            if(maxx>=siz)ans+=cal(cur,index);

        }

        index++;

        printf("%lld\n",ans);

    }

}