-
给定字符串 \(s\)，以及 \(q\) 个串 \(t_i\)，求将 \(s\) 分别与每个 \(t_i\) 拼接起来后，最靠右的 \(|t_i|\) 个前缀的 border 长度。询问间相互独立。
-
\(|s|\leq 10^6, q \leq 10^5, |t_i|\leq 10\) 。
（题面来自洛谷）
看到 border ，第一反应就是 KMP 。又想到 KMP 的 next 数组就是干这件事的，于是就有了一个很逊的想法：每次当做 \(t\) 真的接到了 \(s\) 的后面，对 \(t\) 的字符做 KMP 。看起来复杂度很对，但由于要往回跳，不出七个测试点就会超时。
思考一下，如果跳到了 s 以内的字符，那么实际上跳到哪里是固定的。由于我们只需要对 t 中字符匹配，所以完全可以只存储跳到 s 中每个字符时最终会跳到哪里。
发现 AC 自动机就是干这件事的，于是我们可以对单个字符串建立 AC 自动机。无聊的人类将单个串的 AC 自动机叫做 KMP 自动机。
很棒的一点是由于 AC 自动机单个字符的构建是 \(O(1)\) 的，所以我们可以直接按照上面的很逊的方式构建 AC 自动机。预处理复杂度为 \(O(|S|)\) ，单词询问复杂度为\(O(|T|)\)。
这个优化的本质是将 KMP 中往回跳的路径用 AC 自动机的构造方式进行压缩。
要处理的地方是 \(s\) 与 \(t\) 的交界处。 \(s\) 的最后一个字符的儿子要进行更改，过后也要记得还原。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn =(1 << 20) + 5;
int qian[maxn];
int ch[maxn][26], col[maxn], tot;
int fail[maxn];
void add(string s)
{
int n = s.size(), u = 0;
for(int i = 1;i < n;i ++)
{
int p = s[i] - 'a';
if(!ch[u][p]) ch[u][p] = ++ tot;
u = ch[u][p];
}
col[u] ++;
}
void build()
{
queue<int> q;
for(int i = 0;i < 26;i ++) if(ch[0][i]) q.push(ch[0][i]);
while(!q.empty())
{
int u = q.front();
q.pop();
for(int i = 0;i < 26;i ++)
{
if(!ch[u][i]) ch[u][i] = ch[fail[u]][i];
else fail[ch[u][i]] = ch[fail[u]][i],q.push(ch[u][i]);
}
}
}
int yuan[27];
int main(){
freopen("text.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
string s;
cin >> s;
int n = s.size();
s = ' ' + s;
add(s);
build();
int Q;
cin >> Q;
while(Q --)
{
string t;
cin >> t;
int m = t.size();
t = ' ' + t;
int j = ch[n - 1][s[n] - 'a'];
int p = tot;
for(int i = 0;i < 26;i ++) yuan[i] = ch[tot][i];
for(int i = 1;i <= m;i ++)
{
j = ch[j][t[i] - 'a'];
ch[tot][t[i] - 'a'] = tot + 1;
fail[tot + 1] = ch[fail[tot]][t[i] - 'a'];
cout << j << ' ';
tot ++;
for(int i = 0;i < 26;i ++) ch[tot][i] = ch[fail[tot]][i];
}
for(int i = 0;i < 26;i ++) ch[p][i] = yuan[i];
for(int i = p + 1;i <= tot + 1;i ++)
{
for(int j = 0;j < 26;j ++) ch[i][j] = 0;
if(i != p) fail[i] = 0;
}
tot = p;
cout << endl;
}
return 0;
}