[Codeforces 547E]Cyclical Quest

題目就是給你字串$S$，然後再給你一堆$A_{i}$，問你$S$有幾個子字串和$A_{i}$循環等價

可以考慮對$S$製作後綴自動機
然後對每個$i$ ($1\leq i\leq N$)
把$A_{i}$複製一遍接在後面 (稱新字串為$B$)
讓$B$在自動機裡面進行轉移
可以立即得到當前$B$的前綴屬於$S$的子字串的最長後綴 (請參考這裡)
如果後綴長度$\geq \left|A_{i}\right|$，就把這點標記起來，代表如果某個代表$S$前綴的點可以透過失配邊直接或間接指到這點，那麼這個點代表的$S$前綴的後綴就是符合條件的子字串
當然，因為要找出盡量多符合條件的$S$子字串，所以如果目前節點往失配邊走，代表的字串長度還是$\geq \left|A_{i}\right|$，就得往失配邊走

可以發現
後綴自動機的所有失配邊反向後會形成一棵根為$0$的樹
而答案就是這些被標記的點和其子節點們之中有幾個代表$S$的前綴

我們可以先把這棵樹壓平 ($dfs$並存下進入和離開時間即可)，讓每棵子樹都可以用一個區間來表示
然後用線段樹來維護，可以先預處理，用單點修改將所有代表$S$前綴的點加入
然後要求$u$和其子節點們之中有幾個代表$S$的前綴時，只要線段樹查詢子樹對應的區間的總和就好了

要注意被標記的點中有可能出現某個點是另外一個點的子節點的情況
為了避免重複計算
我們先把標記的點依照$dfs$後序排序 (設序列變成$\{v_{1},v_{2},v_{3},...\}$)，這樣如果$v_{a}$是$v_{b}$的子節點，那麼$v_{a+1},v_{a+2},...,v_{b-1}$也都會是$v_{b}$的子節點
用$stack$維護互不屬於父子關係的節點們即可

時間複雜度：$O(\left|S\right|+\sum_{i=1}^{N}\left|A_{i}\right|)$

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
#include<stack> 
using namespace std;
bool ContainsSegment(const pair<int,int>&a,const pair<int,int>&b)
{
    return a.first<=b.first&&b.second<=a.second;
}
struct SegTree
{
    vector<int>SUM;
    void Build(const int id,const int l,const int r)
    {
        while((int)SUM.size()<=id)SUM.push_back(0);
        SUM[id]=0;
        if(l<r)
        {
            const int mid=(l+r)/2;
            Build(id*2,l,mid),Build(id*2+1,mid+1,r);
        }
    }
    void Add(const int id,const int l,const int r,const int loc)
    {
        SUM[id]++;
        if(l<r)
        {
            const int mid=(l+r)/2;
            if(loc<=mid)Add(id*2,l,mid,loc);
            else Add(id*2+1,mid+1,r,loc);
        }
    }
    int Query(const int id,const int l,const int r,const int bl,const int br)
    {
        if(r<bl||br<l)return 0;
        if(bl<=l&&r<=br)return SUM[id];
        const int mid=(l+r)/2;
        return Query(id*2,l,mid,bl,br)+Query(id*2+1,mid+1,r,bl,br);
    }
};
struct SquashedTree
{
    vector<vector<int> >ET;
    vector<pair<int,int> >SEGS;
    SegTree SEG_TREE;
    int N;
    void Clear(const int _N){N=_N;ET.clear();ET.resize(N),SEGS.resize(N);}
    void Build(const int u,int &tick)
    {
        SEGS[u].first=tick;
        for(const int nxt:ET[u])Build(nxt,tick);
        SEGS[u].second=tick++;
    }
    void Build()
    {
        int tick=0;
        Build(0,tick);
        assert(tick==N);
        SEG_TREE.Build(1,0,N-1);
    }
    void AddTag(const int u)
    {
        SEG_TREE.Add(1,0,N-1,SEGS[u].second);
    }
    int CountTags(const int u)
    {
        return SEG_TREE.Query(1,0,N-1,SEGS[u].first,SEGS[u].second);
    }
};
struct SuffixAutomaton
{
    vector<int>EDGE[26],GREEN,MAX_LEN;
    int N;
    void Clear()
    {
        for(int i=0;i<26;i++)EDGE[i].clear();
        GREEN.clear(),MAX_LEN.clear();
        N=0;
        NewNode(0);
    }
    int NewNode(const int max_len)
    {
        for(int i=0;i<26;i++)EDGE[i].push_back(0);
        GREEN.push_back(-1),MAX_LEN.push_back(max_len);
        return N++;
    }
    int Split(int cur,const int c)
    {
        const int wish=NewNode(MAX_LEN[cur]+1),pg=EDGE[c][cur];
        assert(MAX_LEN[pg]>MAX_LEN[cur]+1);
        for(;cur!=-1&&EDGE[c][cur]==pg;cur=GREEN[cur])EDGE[c][cur]=wish;
        for(int i=0;i<26;i++)EDGE[i][wish]=EDGE[i][pg];
        GREEN[wish]=GREEN[pg];
        GREEN[pg]=wish;
        return wish;
    }
    int Extend(const int u,const int c)
    {
        const int last=NewNode(MAX_LEN[u]+1);
        int cur=u;
        for(;cur!=-1&&!EDGE[c][cur];cur=GREEN[cur])EDGE[c][cur]=last;
        if(cur==-1)GREEN[last]=0;
        else
        {
            const int pg=EDGE[c][cur];
            if(MAX_LEN[pg]==MAX_LEN[cur]+1)GREEN[last]=pg;
            else
            {
                const int tmp=Split(cur,c);//important!
                GREEN[last]=tmp;
            }
        }
        assert(GREEN[last]!=-1);
        return last;
    }
    SquashedTree TREE;
    void Build(const char *str)
    {
        Clear();
        vector<int>vis_nodes;
        for(int i=0,u=0;str[i];i++)vis_nodes.push_back(u=Extend(u,str[i]-'a'));
        TREE.Clear(N);
        for(int i=1;i<N;i++)TREE.ET[GREEN[i]].push_back(i);
        TREE.Build();
        for(const int u:vis_nodes)TREE.AddTag(u);
    }
    int Match(const char *str,const int n)
    {
        vector<int>vis_nodes;
        for(int i=0,u=0,len=0;str[i];i++)
        {
            const int c=str[i]-'a';
            while(u&&!EDGE[c][u])u=GREEN[u],len=MAX_LEN[u];
            if(EDGE[c][u])len++,u=EDGE[c][u];
            if(len>=n)
            {
                while(MAX_LEN[GREEN[u]]>=n)u=GREEN[u],len=MAX_LEN[u];
                vis_nodes.push_back(u);
            }
        }
        sort(vis_nodes.begin(),vis_nodes.end(),
            [this](const int a,const int b)->bool{return TREE.SEGS[a].second<TREE.SEGS[b].second;});
        stack<int>stk;
        for(const int u:vis_nodes)
        {
            while(!stk.empty()&&ContainsSegment(TREE.SEGS[u],TREE.SEGS[stk.top()]))stk.pop();
            stk.push(u);
        }
        int ans=0;
        while(!stk.empty())ans+=TREE.CountTags(stk.top()),stk.pop();
        return ans;
    }
}SAM;
char S[2000000];
int N;
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%s",S)==1)
    {
        SAM.Build(S);
        scanf("%d",&N);
        for(int i=0;i<N;i++)
        {
            scanf("%s",S);
            int len=-1;while(S[++len]);
            for(int i=0;i<len-1;i++)S[len+i]=S[i];
            S[len*2-1]='\0';
            printf("%d\n",SAM.Match(S,len));
        }
    }
    return 0;
}