要提到 KMP 算法，首先得提到字符串相关知识。

字符串相关

概念

前缀/后缀：这个很容易理解。
真前缀/真后缀：就是非原串的前缀/后缀。
子串：从原串中选取连续的一段就是一个子串，空串也算子串。
- 任何子串都是一个前缀的后缀/一个后缀的前缀。
周期：当满足 $s_i=s_{i+p}(1\leqslant i \leqslant |s|-x)$ 时，$x$ 是 $s$ 的周期。
Border：当一个字符串 $t$，既是 $s$ 的前缀，又是 $s$ 的后缀时，$t$ 就是 $s$ 的一个 Border。

性质

当一个字符串 $t$ 为 $s$ 的 Border 时，$|s|-|t|$ 为 $s$ 的一个周期。
Border 具有传递性，即当 $x$ 为 $y$ 的 Border、$y$ 为 $z$ 的 Border 时，必然有 $x$ 为 $z$ 的 Border。
Border 传递性 $2$：当 $x$ 为 $z$ 的 Border、$y$ 为 $z$ 的 Border 时，必然有 $x$ 为 $y$ 的 Border。

字符串匹配

模板：P3375 【模板】KMP。

令 $pre(s,i)$ 表示 $s$ 的长度为 $i$ 的前缀，$suf(s,i)$ 表示 $s$ 的长度为 $i$ 的后缀。

给定两个字符串 $s$ 和 $t$($1\leqslant |s|,|t|\leqslant 10^5$)，现在要查询 $s$ 在 $t$ 中的出现位置有哪些。

暴力匹配 $O(|s| \times |t|)$，爆炸。

我们拿两个指针 $i,j$ 表示 $s[1\cdots i]$ 与 $t[j-i+1\cdots j]$ 完全相同，$j$ 在 $1\sim |t|$ 循环，同时 $i$ 相应变化，始终满足 KMP 性质：$suf(pre(t,j),i)=pre(s,i)$($i$ 越大越好)。

在更新时 $i,j$ 时：

若 $s_{i+1}=t_{j+1}$，则各自后移，i++, j++;，当 $i=n$ 时，$s$ 已经完全匹配，可以推出它的起始位置等。
否则，右移 $j$，调整 $i$，使得 $suf(pre(t,j),i)=pre(s,i)$ 仍然满足，那么该如何调整呢？

Next[] 失配数组

在发生不匹配时，我们需要调整 $i$，这个可以通过预处理来解决，通常定义为 Next 数组，有时也叫 fail 数组(失配数组)。

nxt[i] = max{k | pre(s, k) = suf(pre(s, i), k)}，即 $pre(s,i)$ 的最长 Border。

若 $pre(s,k)$ 为 $pre(s,i)$ 的 Border，则有：

$pre(s,k-1)$ 为 $pre(s,i-1)$ 的 Border。
$s_k=s_i$。

求解方法

假设 $pre(s,i-1)$ 的所有 Border 长度为 $k_1 > k_2 > k3 \cdots $。

需要找到其中最大的 $k$ 使得 $s_{k+1} = s_i$。
此时 nxt[i] = k + 1(即 $pre(s,i)$ 的最长 Border)。

根据定义和 Border 的传递性，$pre(s,i-1)$ 的所有 Border 其实就是 $nxt_{i-1},nxt_{nxt_{i-1}}\cdots$

求 $nxt_i$ 就是 $k=nxt_{i-1}$ 开始检查 $s_{k+1}=s_j$是否成立，不成立就一直往前找 Next。$k= nxt_k$ 然后重复上述判断(找到满足条件的最长 Border)。

Code

void get_fail () {
  for (int i = 2, j = 0; i <= m; i++) {
    while (j && s[i] != s[j + 1]) {
      j = nxt[j];
    }
    if (s[i] == s[j + 1]) {
      j++;
    }
    nxt[i] = j;
  }
}

求完了失配数组，剩下就好办了。

KMP Code

for (int i = 1, j = 0; i <= n; i++) {
  while (j && t[i] != s[j + 1]) {
    j = nxt[j];
  }
  if (t[i] == s[j + 1]) {
    j++;
  }
  if (j == m) {
    cout << i - j + 1 << '\n';
  }
}

模板完整代码

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n, m, nxt[N];
string s, t;

void get_fail () {
  for (int i = 2, j = 0; i <= m; i++) {
    while (j && s[i] != s[j + 1]) {
      j = nxt[j];
    }
    if (s[i] == s[j + 1]) {
      j++;
    }
    nxt[i] = j;
  }
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> t >> s, n = t.size(), m = s.size(), s = " " + s, t = " " + t;
  get_fail();
  for (int i = 1, j = 0; i <= n; i++) {
    while (j && t[i] != s[j + 1]) {
      j = nxt[j];
    }
    if (t[i] == s[j + 1]) {
      j++;
    }
    if (j == m) {
      cout << i - j + 1 << '\n';
    }
  }
  for (int i = 1; i <= m; i++) {
    cout << nxt[i] << ' ';
  }
  return 0;
}

时间复杂度：$O(|s|+|t|)$。