记录编号	447956	评测结果	AAAAAAAAAA
题目名称	循环同构	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.250 s
提交时间	2017-09-11 20:23:04	内存使用	442.82 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;
}
vector<int> v[N];
int rank(int x,vector<int>& a){
    int l=0,r=a.size()-1;
    while (l<r){
        int mid=(l+r)>>1;
        if (x>a[mid+1]) l=mid+1;else r=mid;
    }
    return a.size()-l-1;
}
int cnt[N],size[N],val[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,now=0;i<s.size();i++){
        int w=s[i]-'a';
        while (p&&!go[p][w]) p=par[p],now=len[p];
        if (p) p=go[p][w],now++;else p=1;
        size[p]++;val[p]++;
        v[p].push_back(now);
    }
    for (int i=1;i<=top;i++) v[i].push_back(0),sort(v[i].begin(),v[i].end());
    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]-val[x]+rank(S[i].size(),v[x]));
        }
        printf("%d\n",ans);
    }
    return 0;
}