CF 235C. Cyclical Quest [后缀自动机]

题意：给一个主串和多个询问串，求询问串的所有样子不同的周期同构出现次数和

---

没有周期同构很简单就是询问串出现次数，|Right|

有了周期同构，就是所有循环，把询问串复制一遍贴到后面啊！思想和POJ1509相似，不要局限于复制主串

然后走的时候维护nowLen

需要支持尾部插入字符(走转移边)和首部删除字符(走parent边)就行了

PS：家里上CF太慢了还是学校网速快

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

using namespace std;

#define lc x<<1

#define rc x<<1|1

#define mid ((l+r)>>1)

#define lson lc,l,mid

#define rson rc,mid+1,r

const int N=2e6+;

typedef long long ll;

int n,ri[N];

char s[N];

struct node{

    int ch[],par,val;

}t[N];

int sz=,root=,last=;

void extend(int c){

    int p=last,np=++sz;

    t[np].val=t[p].val+; ri[np]++;

    for(;p&&!t[p].ch[c];p=t[p].par) t[p].ch[c]=np;

    if(!p) t[np].par=root;

    else{

        int q=t[p].ch[c];

        if(t[q].val==t[p].val+) t[np].par=q;

        else{

            int nq=++sz;

            t[nq]=t[q];t[nq].val=t[p].val+;

            t[q].par=t[np].par=nq;

            for(;p&&t[p].ch[c]==q;p=t[p].par) t[p].ch[c]=nq;

        }

    }

    last=np;

}

int vis[N];

void walk(int id){//puts("walk");

    int u=root,len=n+n-,ans=,nowLen=;

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

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

        if(t[u].ch[c]) u=t[u].ch[c],nowLen++;

        else{

            while(u&&!t[u].ch[c]) u=t[u].par;

            if(!u) u=root,nowLen=;

            else nowLen=t[u].val+,u=t[u].ch[c];

        }

        //printf("i %d %d  %d  %d\n",i,c,u,nowLen);

        if(vis[u]!=id&&nowLen>=n) vis[u]=id,ans+=ri[u];//,printf("ans %d %d\n",u,ri[u]);

        if(n!=) while(t[t[u].par].val+>=n) u=t[u].par,nowLen=t[u].val;

        //printf("nowu %d\n",u);

    }

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

}

int c[N],a[N];

void RadixSort(){

    for(int i=;i<=sz;i++) c[t[i].val]++;

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

    for(int i=sz;i>=;i--) a[c[t[i].val]--]=i;

}

void solve(){

    RadixSort();

    int u;

    for(int i=sz;i>=;i--) u=a[i],ri[t[u].par]+=ri[u];

    int m;scanf("%d",&m);

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

        scanf("%s",s+);

        n=strlen(s+);

        for(int i=;i<n;i++) s[i+n]=s[i];

        walk(i);

    }

}

int main(){

    //freopen("in","r",stdin);

    scanf("%s",s+);

    n=strlen(s+);

    for(int i=;i<=n;i++) extend(s[i]-'a');

    solve();

}