发现字符串啥也不会。。
设原串为 \(s\)，\(nxt_{i,j}\) 表示从 \(i\) 开始沿着 fail 树向上跳的到的最大位置 \(k\) 满足 \(s_{k+1}=j\)，若不存在则为 \(0\)。
注意到 KMP 求前缀函数其实也是跳 fail 树的过程：对于 \(i\)，从 \(fail_{i-1}\) 开始沿着 fail 树向上跳，找到最大的位置 \(k\) 满足 \(s_{k+1}=j\)，若不存在则为 \(0\)。
处理出 \(fail\) 函数后可以由此推出 \(nxt_{i,j}\)：
- 若 \(s_{i+1}=j\)，则 \(nxt_{i,j}=i\)。
- 否则 \(nxt_{i,j}=nxt_{fail_i,j}\)。
那么每次扫一遍询问串，跑一遍 KMP，如果当前指针在 \(n\) 以内就用预处理出的 \(nxt\) 数组 \(\mathcal O(1)\) 转移。单次询问 \(\mathcal O(\left|t\right|)\)。
具体细节看代码。
Code：
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005, M = 26;
int n, Q;
int fail[N + 10], nxt[N][M];
char s[N + 10];
void prework() {
for (int i = 2, j = 0; i <= n; ++i) {
while (j && s[j + 1] != s[i]) j = fail[j];
if (s[j + 1] == s[i]) ++j;
fail[i] = j;
}
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 26; ++j) {
if (i != n && s[i + 1] == char('a' + j)) nxt[i][j] = i;
else nxt[i][j] = nxt[fail[i]][j];
}
}
}
void solve() {
scanf("%s", &s[n + 1]);
int m = strlen(&s[n + 1]);
for (int i = n + 1, j = fail[n]; i <= n + m; ++i) {
while (j && s[j + 1] != s[i]) {
if (j <= n) { j = nxt[j][s[i] - 'a']; break; }
j = fail[j];
}
if (s[j + 1] == s[i]) ++j;
printf("%d ", fail[i] = j);
}
printf("\n");
}
int main() {
scanf("%s%d", s + 1, &Q), n = strlen(s + 1);
prework();
while (Q--) solve();
return 0;
}