#include<bits/stdc++.h>
using namespace std;
namespace my_IO{
    #define ll long long
    #define ull unsigned long long
    #define ld long double
    #define et putchar('\n')
    #define spc putchar(' ')
    template<class T>
    void read(T &num){
        T x=0,f=1;
        char c=getchar();
        while(!isdigit(c)){
            if(c=='-') f=-1;
            c=getchar();
        }
        while(isdigit(c)){
            x=(x<<3)+(x<<1)+c-48;
            c=getchar();
        }
        num=f*x;
    }
    template<class T>
    void write(T x){
        static char buf[40];
        static int len=-1;
        if(x<0) putchar('-'),x=-x;
        do{
            buf[++len]=x%10+48;
            x/=10;
        }while(x);
        while(len>=0) putchar(buf[len--]);
    }
}
using namespace my_IO;
const int maxn=1e6+10;
int q,cnt,lst,head[maxn<<1],tot,siz[maxn<<1],vis[maxn],tp,stk[maxn];
struct edge{
    int t,nxt;
}e[maxn<<1];
void add(int st,int ed){
    e[++tot]={ed,head[st]};
    head[st]=tot;
}
struct nd{
    int len,link;
    map<char,int> to;
}sam[maxn<<1];
void init(){
    sam[0].link=-1;
}
void insert(char c){
    int cur=++cnt,p=lst;
    sam[cur].len=sam[p].len+1;
    siz[cur]=1;
    while(p!=-1&&!sam[p].to[c]){
        sam[p].to[c]=cur;
        p=sam[p].link;
    }
    if(p==-1) sam[cur].link=0;
    else{
        int q=sam[p].to[c];
        if(sam[q].len==sam[p].len+1) sam[cur].link=q;
        else{
            int clone=++cnt;
            sam[clone].link=sam[q].link;
            sam[clone].to=sam[q].to;
            sam[clone].len=sam[p].len+1;
            sam[cur].link=sam[q].link=clone;
            while(p!=-1&&sam[p].to[c]==q){
                sam[p].to[c]=clone;
                p=sam[p].link;
            }
        }
    }
    lst=cur;
}
void dfs(int u){
    for(int i=head[u];i;i=e[i].nxt){
        dfs(e[i].t);
        siz[u]+=siz[e[i].t];
    }
}
void build(string s){
    for(auto c:s) insert(c);
}
int query(string s){
    int now=0,len=0,m=s.size(),ans=0;
    s=s+s;
    for(auto c:s){
        if(sam[now].to[c]){
            now=sam[now].to[c];
            len++;
        }
        else{
            int p=now;
            while(p!=-1&&!sam[p].to[c]) p=sam[p].link;
            if(p==-1) now=0,len=0;
            else now=sam[p].to[c],len=sam[p].len+1;
        }
        while(sam[now].link!=-1&&sam[sam[now].link].len>=m) now=sam[now].link;
        if(!vis[now]&&len>=m){
            ans+=siz[now];
            vis[now]=1;
            stk[++tp]=now;
        }
        // cout<<now<<" "<<ans<<"\n";
    }
    while(tp){
        vis[stk[tp]]=0;
        tp--;
    }
    return ans;
}
int main(){
    init();
    string s;
    cin>>s;
    build(s);
    // for(int i=0;i<=cnt;i++){
    //     cout<<i<<" "<<sam[i].link<<":\n";
    //     for(auto it:sam[i].to) cout<<it.first<<" "<<it.second<<"\n";
    // }
    for(int i=1;i<=cnt;i++) add(sam[i].link,i);
    dfs(0);
    // for(int i=1;i<=cnt;i++) cout<<i<<" "<<siz[i]<<"\n";
    read(q);
    while(q--){
        cin>>s;
        write(query(s)),et;
    }
}

悬赏一关注