/*
统计串的出现次数显然可以在自动机上匹配出来即可
但是每次都挨个匹配的话会时间爆炸

那么考虑我们把串复制一份， 然后一起在后缀自动机上跑， 当我们匹配长度大于该串长度的时候强行失配即可

可能会有旋转后相同的串所以开个数组判重 


*/

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<iostream>
#define ll long long 
#define M 2000100 
#define mmp make_pair
using namespace std;
int read()
{
    int nm = 0, f = 1;
    char c = getchar();
    for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
    return nm * f;
}
char s[M];
int ch[M][26], fa[M], len[M], sz[M], tot[M], a[M], lst = 1, cnt = 1;
int vis[M];

void insert(int c)
{
    int p = ++cnt, f = lst;
    lst = p;
    len[p] = len[f] + 1;
    sz[p] = 1;
    while(f && !ch[f][c]) ch[f][c] = p, f = fa[f];
    if(!f)
    {
        fa[p] = 1;
    }
    else
    {
        int q = ch[f][c];
        if(len[q] == len[f] + 1)
        {
            fa[p] = q;
        }
        else
        {
            int nq = ++cnt;
            memcpy(ch[nq], ch[q], sizeof(ch[q]));
            fa[nq] = fa[q];
            len[nq] = len[f] + 1;
            fa[p] = fa[q] = nq;
            while(f && ch[f][c] == q) ch[f][c] = nq, f = fa[f];
        }
    }
}


int main()
{
    scanf("%s", s + 1);
    int l = strlen(s + 1);
    for(int i = 1; i <= l; i++) insert(s[i] - 'a');
    for(int i = 1; i <= cnt; i++) tot[len[i]]++;
    for(int i = 1; i <= cnt; i++) tot[i] += tot[i - 1];
    for(int i = 1; i <= cnt; i++) a[tot[len[i]]--] = i;
    for(int i = cnt; i >= 1; i--) sz[fa[a[i]]] += sz[a[i]];
    int m = read();
    for(int cor = 1; cor <= m; cor++)
    {
        scanf("%s", s + 1);
        l = strlen(s + 1);
        for(int i = 1; i <= l; i++) s[l + i] = s[i];
        int now = 1, lenn = 0;
        ll ans = 0;
        for(int i = 1; i <= l * 2; i++)
        {
            int c = s[i] - 'a';
            while(now && !ch[now][c]) now = fa[now], lenn = len[now];
            if(!now) now = 1, lenn = 0;
            else now = ch[now][c], lenn++;
            while(now && len[fa[now]] >= l) now = fa[now], lenn = len[now]; //只能统计那些刚刚超过的节点 
            if(lenn >= l && vis[now] != cor) vis[now] = cor, ans += sz[now]; 
        }
        cout << ans << "\n";
    }
    return 0;
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄