Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- const int N=200005;
- int tot;
- int Max[N];
- int Min[N];
- int to[N][26];
- int fa[N];
- int siz[N];
- inline int NewNode(int mx,int mi,int *tr,int su,bool f){
- ++tot;
- Max[tot]=mx;
- Min[tot]=mi;
- if(tr!=NULL)memcpy(to[tot],tr,26<<2);
- fa[tot]=su;
- siz[tot]=f;
- return tot;
- }
- inline int insert(int u,int c){
- int t=NewNode(Max[u]+1,0,NULL,0,1);
- for(;u&&!to[u][c];u=fa[u])to[u][c]=t;
- if(!u){
- Min[t]=1;
- fa[t]=1;
- return t;
- }
- int v=to[u][c];
- if(Max[v]==Max[u]+1){
- Min[t]=Max[v]+1;
- fa[t]=v;
- return t;
- }
- int x=NewNode(Max[u]+1,0,to[v],fa[v],0);
- Min[t]=Min[v]=Max[x]+1;
- fa[t]=fa[v]=x;
- Min[x]=Max[fa[x]]+1;
- for(;u&&to[u][c]==v;u=fa[u])to[u][c]=x;
- return t;
- }
- char s[N];
- int deg[N];
- bool vis[N];
- queue<int>Q;
- int main(){
- // freopen(".in","r",stdin);
- // freopen(".out","w",stdout);
- scanf("%s",s);
- int n=strlen(s);
- int lst=NewNode(0,0,NULL,0,0);
- for(int i=0;i<n;++i){
- lst=insert(lst,s[i]-'a');
- }
- for(int i=2;i<=tot;++i){
- ++deg[fa[i]];
- }
- for(int i=1;i<=tot;++i){
- if(!deg[i]){
- Q.push(i);
- }
- }
- while(!Q.empty()){
- int x=Q.front();Q.pop();
- if(!fa[x])continue;
- siz[fa[x]]+=siz[x];
- if(!--deg[fa[x]]){
- Q.push(fa[x]);
- }
- }
- int q;
- for(scanf("%d",&q);q;--q){
- memset(vis+1,0,tot);
- scanf("%s",s);
- n=strlen(s);
- memcpy(s+n,s,sizeof(char)*n);
- int m=n<<1;
- int ans=0;
- int u=1,l=0;
- for(int i=0;i<m;++i){
- int c=s[i]-'a';
- while(u!=1&&!to[u][c])u=fa[u],l=Max[u];
- if(to[u][c])u=to[u][c],++l;
- if(l>n){
- while(Min[u]>n)u=fa[u];
- }
- if(l>=n&&!vis[u]){
- ans+=siz[u];
- vis[u]=1;
- }
- }
- printf("%d\n",ans);
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment