首先对 \(s\) 建 SAM，设 \(m = |t|\)，然后考虑断环为链，把询问串 \(t\) 再复制一份拼接在后面，然后相当于问现在 \(t\) 的所有长度为 \(m\) 的本质不同子串在 \(s\) 中的出现次数之和。
考虑枚举子串的右端点，维护当前在 SAM 上的结点 \(u\)，每次尝试将匹配长度 \(+1\)。如果匹配长度 \(> m\) 那么需要“删除”开头的一些字符，如果匹配长度 \(= m\) 那么就将 \(\text{sz}(u)\) 累加进答案，同时标记 \(u\) 为了不重复访问（所有长度固定的串在 SAM 上对应的结点一定两两不同）。
考虑如何“删除”字符。我们发现 \(\text{link}(u)\) 恰好满足我们的需求，因为 \(\text{link}(u)\) 的定义为 SAM 上对应于 \(u\) 代表的集合的串的最长后缀的另一个 \(\text{endpos}\) 等价类的状态，所以当 \(\text{len}(\text{link}(u)) \ge m\) 时我们就令 \(u \gets \text{link}(u)\) 即可。
所以总时间复杂度就是 \(O(n + \sum m)\)。
code
// Problem: C. Cyclical Quest
// Contest: Codeforces - Codeforces Round 146 (Div. 1)
// URL: https://codeforces.com/problemset/problem/235/C
// Memory Limit: 512 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 2000100;
int n, m, K;
char s[maxn], t[maxn];
struct SAM {
int lst, tot, ch[maxn][26], fa[maxn], len[maxn], sz[maxn], stk[maxn], top;
bool vis[maxn];
vector<int> G[maxn];
inline void init() {
for (int i = 1; i <= tot; ++i) {
fa[i] = len[i] = sz[i] = 0;
vector<int>().swap(G[i]);
mems(ch[i], 0);
}
lst = tot = 1;
}
inline void insert(int k, int c) {
int u = ++tot, p = lst;
sz[u] = 1;
lst = u;
len[u] = k;
for (; p && !ch[p][c]; p = fa[p]) {
ch[p][c] = u;
}
if (!p) {
fa[u] = 1;
return;
}
int q = ch[p][c];
if (len[q] == len[p] + 1) {
fa[u] = q;
return;
}
int nq = ++tot;
fa[nq] = fa[q];
memcpy(ch[nq], ch[q], sizeof(ch[nq]));
len[nq] = len[p] + 1;
fa[u] = fa[q] = nq;
for (; p && ch[p][c] == q; p = fa[p]) {
ch[p][c] = nq;
}
}
void dfs(int u) {
for (int v : G[u]) {
dfs(v);
sz[u] += sz[v];
}
}
inline void build() {
for (int i = 2; i <= tot; ++i) {
G[fa[i]].pb(i);
}
dfs(1);
}
inline ll solve() {
int p = 1, k = 0;
ll ans = 0;
top = 0;
for (int i = 1; i <= K * 2 - 1; ++i) {
int c = t[i] - 'a';
if (ch[p][c]) {
p = ch[p][c];
++k;
} else {
while (p && !ch[p][c]) {
p = fa[p];
}
if (p) {
k = len[p] + 1;
p = ch[p][c];
} else {
k = 0;
p = 1;
}
}
k = min(k, K);
while (len[fa[p]] >= K) {
p = fa[p];
}
if (k >= K && !vis[p]) {
stk[++top] = p;
vis[p] = 1;
ans += sz[p];
}
}
while (top) {
vis[stk[top]] = 0;
stk[top--] = 0;
}
return ans;
}
} sam;
void solve() {
scanf("%s%d", s + 1, &m);
n = strlen(s + 1);
sam.init();
for (int i = 1; i <= n; ++i) {
sam.insert(i, s[i] - 'a');
}
sam.build();
while (m--) {
scanf("%s", t + 1);
K = strlen(t + 1);
for (int i = K + 1; i <= K * 2 - 1; ++i) {
t[i] = t[i - K];
}
printf("%lld\n", sam.solve());
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}