§04 串与数组
串的模式匹配
在长文本中查找模式串，KMP 比暴力匹配高明在：先求出模式串的 next 数组， 匹配失配时让模式整体右滑、文本指针 i 从不回退。整体复杂度 O(n + m)， next 数组记录的正是模式串自身的前后缀结构。
串的模式匹配
伪代码
1
procedure getNext(t, m, next)
2
j = 1; k = 0; next[1] = 0
3
while j < m do
4
if k = 0 或 t[j] = t[k] then
5
j++; k++; next[j] = k
6
else
7
k = next[k] // 前缀回退
8
end while
9
procedure KMP(s, n, t, m)
10
i = 1; j = 1
11
while i <= n 且 j <= m do
12
if j = 0 或 s[i] = t[j] then
13
i++; j++
14
else
15
j = next[j] // 模式右滑，i 不回退
16
end while
17
if j > m then return i - m
18
else return 0