[Codeforces Round #146 (Div. 1)] Cyclical Quest

題目連結

題目要求在一給定字串S上求出某一字串T的所有循環字串出現幾次
(此處循環字串的意義詳見原題)

不多說，把S的後綴自動機炸出來，然後為了處理循環問題把詢問的字串都複製一次
然後在自動機上轉移狀態，要維護的東西和實做原理其實和一般的字串matching沒什麼不同，只是用後綴自動機實現
唯一要注意的二點
1.同一個狀態的結束集合大小只能計算1次，否則像aa等等會有某循環字串被詢問到2次時會重複算
2.當cnt>=原詢問字串長度(m)時，由於可能當前狀態的fail的Max仍然>=m，不過fail的結束集合大小會變大，此時就要直接轉移到fail，否則答案會少許多......

#include<bits/stdc++.h>
using namespace std;
const int maxnode=2000000+5;
const int SIGMA_SIZE=26;
struct Node
{
    Node *fail,*ch[SIGMA_SIZE];
    int Max,End,vis;
    Node() {fail=0;Max=vis=End=0;memset(ch,0,sizeof ch);}
} mem[maxnode],*root,*last;
struct SuffixAutomaton
{
    int size,scnt;
    inline int idx(char c) {return c-'a';}
    inline void init() {size=scnt=0;root=last=&mem[0];}
    inline void add(char c)
    {
        c=idx(c);
        Node *p=last;
        Node *np=&mem[++size];np->Max=p->Max+1;
        while(p && !p->ch[c]) p->ch[c]=np,p=p->fail;
        if(!p) np->fail=root;
        else
        {
            Node *q=p->ch[c];
            if(q->Max==p->Max+1) np->fail=q;
            else
            {
                Node *nq=&mem[++size];nq->Max=p->Max+1;
                memcpy(nq->ch,q->ch,sizeof(q->ch));
                nq->fail=q->fail;
                q->fail=np->fail=nq;
                while(p && p->ch[c]==q) p->ch[c]=nq,p=p->fail;
            }
        }
        last=np;
    }
    int C[maxnode],ord[maxnode];
    void topo_cal(char* s,int n)
    {
        for(int i=0;i<=size;i++) C[mem[i].Max]++;
        for(int i=1;i<=size;i++) C[i]+=C[i-1];
        for(int i=0;i<=size;i++) ord[--C[mem[i].Max]]=i;
        Node* now=root;
        for(int i=0;i<n;i++)
        {
            int c=idx(s[i]);
            now=now->ch[c];
            now->End=1;
        }
        for(int i=size;i>=0;i--)
        {
            now=&mem[ord[i]];
            if(now->fail) now->fail->End+=now->End;
        }
    }
    inline void solve(char* s)
    {
        scnt++;
        int n=strlen(s),cnt=0,ans=0;
        Node* now=root;
        for(int i=0;i<n-1;i++)
        {
            int c=idx(s[i]);
            if(now->ch[c]) cnt++,now=now->ch[c];
            else
            {
                while(now && !now->ch[c]) now=now->fail;
                if(!now) cnt=0,now=root;
                else cnt=now->Max+1,now=now->ch[c];
            }
            while(cnt>=n/2 && now->fail && now->fail->Max>=n/2) cnt=now->fail->Max,now=now->fail;
            if(cnt>=n/2 && now->vis!=scnt) ans+=now->End,now->vis=scnt;
        }
        printf("%d\n",ans);
    }
}SAM;
const int maxlen=1000000+5;
char s[maxlen*2];
int main()
{
    SAM.init();
    scanf("%s",s);
    int n=strlen(s),T;
    for(int i=0;i<n;i++) SAM.add(s[i]);
    SAM.topo_cal(s,n);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s);
        n=strlen(s);
        for(int i=0;i<n;i++) s[i+n]=s[i];
        s[n*2]='\0';
        SAM.solve(s);
    }
}