A: a b a b a b a a b a b ...
B: a b a b a c b
此时 $A[6]\neq B[6]$，调整 $j$ 。
想一想，调整的这个 $j$ 应该使得 B 中前 $j$ 个和后 $j$ 个相等（因为把 B “移” 过去之后依然匹配）
考虑对每个 B 中的位置预处理一个 $P[i]$，表示当位置 $i$ 失配时，$i$ 应该调整到多少。
而预处理 $P$ 的过程相当于 B 自己匹配自己。
**适用场景：一个模式串，多个主串。**
## 【code】
```
//预处理
p[1] = 0;
j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && B[j + 1] != B[i + 1])
j = p[j];
if (B[j + 1] == B[i + 1])
j++;
p[i + 1] = j;
}
//主程序
j = 0;
for (int i = 1; i < n; i++) {
while (j > 0 && B[j + 1] != A[i + 1])
j = p[j];
if (B[j + 1] == A[i + 1])
j++;
if (j == m) { //匹配成功
cout << i + 1 - m + 1 << endl; //子串串首位置
j = p[j];
}
}
```
## 【AC 自动机】
AC 自动机 = Trie + KMP
AC 自动机用来处理多模匹配的问题：
给出 $n$ 个单词和一篇文章，询问每个单词是否出现在文章中。
先把模式串建成一棵 Trie 。
```
void make() {
int len = strlen(s), u = 1;
for (int i = 0; i < len; i++) {
int c = s[i] - 'A';
if (!ch[u][c])
ch[u][c] = ++tot;
u = ch[u][c]
}
bo[u] = 1; //末端标记
}
```
考虑在每个结点上记录一个 $nxt$，表示当这个结点失配时，要跳到哪个节点。
因为 $deep[nxt[u]]<deep[u]$，所以我们可以按照 BFS 顺序更新。
```
void bfs() {
for (int i = 0; i <= 25; i++)
ch[0][i] = 1;
que[1] = 1;
nxt[1] = 0;
for (int q1 = 1, q2 = 1; q1 <= q2; q1++) {
int u = que[q1];
for (int i = 0; i <= 25; i++) {
if (!ch[u][i])
ch[u][i] = ch[nxt[u]][i];
else {
que[++q2] = ch[u][i];
int v = nxt[u];
while (v > 0 && !ch[v][i])
v = nxt[v];
nxt[ch[u][i]] = ch[v][i];
}
}
}
}
```
不存在 $u$ 的转移边 $i$ 时，我们直接跳到 $ch[nxt[u]][i]$，可以优化时间。
因为我们本来需要往前走到一个点再跳回去，不如现在跳。
查询：
```
int fnd() {
int u = 1;
for (int i = 1; i <= m; i++) {
u = ch[u][a[i]];
if (bo[u])
return true; //存在
}
return 0;
}
```