yicongli

HIHO1465

Mar 7th, 2019
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.61 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6.  
  7. const int N=200005;
  8.  
  9. int tot;
  10.  
  11. int Max[N];
  12. int Min[N];
  13. int to[N][26];
  14. int fa[N];
  15. int siz[N];
  16.  
  17. inline int NewNode(int mx,int mi,int *tr,int su,bool f){
  18.     ++tot;
  19.     Max[tot]=mx;
  20.     Min[tot]=mi;
  21.     if(tr!=NULL)memcpy(to[tot],tr,26<<2);
  22.     fa[tot]=su;
  23.     siz[tot]=f;
  24.     return tot;
  25. }
  26.  
  27. inline int insert(int u,int c){
  28.     int t=NewNode(Max[u]+1,0,NULL,0,1);
  29.     for(;u&&!to[u][c];u=fa[u])to[u][c]=t;
  30.     if(!u){
  31.         Min[t]=1;
  32.         fa[t]=1;
  33.         return t;
  34.     }
  35.     int v=to[u][c];
  36.     if(Max[v]==Max[u]+1){
  37.         Min[t]=Max[v]+1;
  38.         fa[t]=v;
  39.         return t;
  40.     }
  41.     int x=NewNode(Max[u]+1,0,to[v],fa[v],0);
  42.     Min[t]=Min[v]=Max[x]+1;
  43.     fa[t]=fa[v]=x;
  44.     Min[x]=Max[fa[x]]+1;
  45.     for(;u&&to[u][c]==v;u=fa[u])to[u][c]=x;
  46.     return t;
  47. }
  48.  
  49. char s[N];
  50. int deg[N];
  51. bool vis[N];
  52. queue<int>Q;
  53.  
  54. int main(){
  55. //  freopen(".in","r",stdin);
  56. //  freopen(".out","w",stdout);
  57.     scanf("%s",s);
  58.     int n=strlen(s);
  59.     int lst=NewNode(0,0,NULL,0,0);
  60.     for(int i=0;i<n;++i){
  61.         lst=insert(lst,s[i]-'a');
  62.     }
  63.     for(int i=2;i<=tot;++i){
  64.         ++deg[fa[i]];
  65.     }
  66.     for(int i=1;i<=tot;++i){
  67.         if(!deg[i]){
  68.             Q.push(i);
  69.         }
  70.     }
  71.     while(!Q.empty()){
  72.         int x=Q.front();Q.pop();
  73.         if(!fa[x])continue;
  74.         siz[fa[x]]+=siz[x];
  75.         if(!--deg[fa[x]]){
  76.             Q.push(fa[x]);
  77.         }
  78.     }
  79.     int q;
  80.     for(scanf("%d",&q);q;--q){
  81.         memset(vis+1,0,tot);
  82.         scanf("%s",s);
  83.         n=strlen(s);
  84.         memcpy(s+n,s,sizeof(char)*n);
  85.         int m=n<<1;
  86.         int ans=0;
  87.         int u=1,l=0;
  88.         for(int i=0;i<m;++i){
  89.             int c=s[i]-'a';
  90.             while(u!=1&&!to[u][c])u=fa[u],l=Max[u];
  91.             if(to[u][c])u=to[u][c],++l;
  92.             if(l>n){
  93.                 while(Min[u]>n)u=fa[u];
  94.             }
  95.             if(l>=n&&!vis[u]){
  96.                 ans+=siz[u];
  97.                 vis[u]=1;
  98.             }
  99.         }
  100.         printf("%d\n",ans);
  101.     }
  102.     return 0;
  103. }
Add Comment
Please, Sign In to add comment