记录编号	447934	评测结果	WWWWWWWWWW
题目名称	2399.循环同构	最终得分	0
用户昵称	FoolMike	是否通过	未通过
代码语言	C++	运行时间	1.453 s
提交时间	2017-09-11 19:40:05	内存使用	412.30 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
string S[N],s;
int n,m,L,go[N][26],par[N],len[N],last,top;
int New(int L){len[++top]=L;return top;}
void extend(int w){
    int p=last,np=New(len[p]+1);
    while (p&&!go[p][w]) go[p][w]=np,p=par[p];
    if (!p) par[np]=1;
    else{
        int q=go[p][w];
        if (len[q]==len[p]+1) par[np]=q;
        else{
            int nq=New(len[p]+1);
            memcpy(go[nq],go[q],sizeof go[q]);
            par[nq]=par[q];
            par[np]=par[q]=nq;
            while (p&&go[p][w]==q) go[p][w]=nq,p=par[p];
        }
    }
    last=np;
}
int cnt[N],size[N],q[N],dp[21][N],vis[N];
int gettop(int x,int h){
    for (int i=20;len[par[x]]>=h;x=dp[i][x])
        while (len[dp[i][x]]<h) i--;
    return x;
}
int main()
{
    freopen("rotate.in","r",stdin);
    freopen("rotate.out","w",stdout);
    cin.sync_with_stdio(false);
    cin>>s>>n;
    last=New(0);
    for (int i=1;i<=n;i++){
        cin>>S[i];
        last=1;
        for (int j=0;j<S[i].size();j++) extend(S[i][j]-'a');
        for (int j=0;j<S[i].size();j++) extend(S[i][j]-'a');
    }
    for (int i=0,p=1;i<s.size();i++){
        int w=s[i]-'a';
        while (p&&!go[p][w]) p=par[p];
        p=p?go[p][w]:1;
        size[p]++;
    }
    for (int i=1;i<=top;i++) cnt[len[i]]++;
    for (int i=1;i<=top;i++) cnt[i]+=cnt[i-1];
    for (int i=1;i<=top;i++) q[cnt[len[i]]--]=i;
    for (int i=top;i;i--) size[par[q[i]]]+=size[q[i]];
    for (int i=1;i<=top;i++) dp[0][i]=par[i];
    for (int j=1;j<21;j++)
    for (int i=1;i<=top;i++)
        dp[j][i]=dp[j-1][dp[j-1][i]];
    for (int i=1;i<=n;i++){
        int p=1;
        for (int j=0;j<S[i].size();j++) p=go[p][S[i][j]-'a'];
        int ans=0;
        for (int j=0;j<S[i].size();j++){
            p=go[p][S[i][j]-'a'];
            int x=gettop(p,S[i].size());
            if (vis[x]==i) continue;
            vis[x]=i;
            ans+=size[x];
        }
        printf("%d\n",ans);
    }
    return 0;
}