KMP 算法是用来求模式字符串 $p$ 是否在某个查询字符串 $s$ 中的。设 $len(p) = m, len(s) = n$，则此算法的复杂度为 $O(m+n)$。

KMP 算法并不完全是大部分编程语言的默认匹配算法。由于它需要初始化一个 next 数组（fail 数组），会因为初始化开销过大而被其他算法替代。例如 CPython 中使用的就是 boyer-moore 算法和 horspool 算法的混合版本。但是 KMP 算法的复杂度和代码量都比较小，刷题时很有帮助。

next 数组 Link to heading

next 数组是用来加速字符串匹配速度的，当某次字符串匹配失败时，如果从第 0 个字符重新开始匹配速度太慢，可以考虑利用一些额外信息。

next[i] 考虑为，对于模式字符串的子串 p[0] ~ p[i]，子串前后缀相同的最长长度 k（k 不能为 i+1，因为此时前后缀都是子串本身了）。

例如：“abc” 的 next 数组就是 [0,0,0]，因为不管对于哪个子串，前后缀相同的最长长度都是 0。“abcabc” 的 next 数组是 [0,0,0,1,2,3]，子串 “abcab”，有前缀 “ab” 等于后缀 “ab”。

利用 next 数组 Link to heading

依旧利用 BF 方法进行匹配。但当出现字符不相等的情况时，将模式字符串的指针回溯到 next[pos-1] 的位置。因为我们是在匹配 p[pos] 出现不相等的，但是 p[0] ~ p[pos-1] 都是相等的。如果 next[pos-1] > 0，那么说明 p[0] ~ p[pos-1] 中有 next[pos-1] 个字符首尾相同。那我们就直接从 p[next[pos-1]] 再开始匹配就好啦（首尾相同的后一个）。

代码 Link to heading

 1def kmp(s, p):
 2  nxt = [0]
 3  x = 1     # 字符串尾指针
 4  now = 0   # nxt 匹配位置
 5
 6  while x < len(p):
 7    if p[x] == p[now]:
 8      x += 1
 9      now += 1
10      nxt.append(now)
11    elif now:
12      now = nxt[now-1]
13    else:
14      x += 1
15      nxt.append(0)
16
17  tar = 0
18  pos = 0
19  while tar < len(s):
20    if s[tar] == p[pos]:
21      tar += 1
22      pos += 1
23      if pos == len(p):
24        yield (tar - pos)
25        pos = nxt[pos-1]
26    elif pos:
27      pos = nxt[pos-1]
28    else:
29      tar += 1

 1function *KMP(s: string, p: string) {
 2  const nxt = [0]
 3
 4  let x = 1, now = 0
 5  while (x < len(p)) {
 6    if (p[x] === p[now]) {
 7      x++, now++
 8      nxt.append(now)
 9    } else if (now) {
10      now = nxt[now-1]
11    } else {
12      x++
13      nxt.append(0)
14    }
15  }
16
17  let pos = 0, tar = 0
18  while (tar < len(s)) {
19    if (s[tar] === p[pos]) {
20      tar++, pos++
21      if (pos == len(p)) {
22        yield tar - pos
23        pos = nxt[pos-1]
24      }
25    } else if (pos) {
26      pos = nxt[pos-1]
27    } else {
28      tar += 1
29    }
30  }
31}