字符串——KMP算法
KMP算法问题类型
给定两个字符串，寻找其中一个字符串是否包含另一个字符串，如果包含，返回包含的起始位置。 如下面两个字符串：
char *T = "bacbababadababacambabacaddababacasdsd";
char *P = "ababababca";
普通暴力搜索的时间复杂度为O(mn)，在暴力搜索中有大量重复搜索，KMP通过引入next数组大大降低了时间复杂度。
算法简述
后缀 对任意 $i∈[0, m - 1]$，$S[i ,m - 1]$ 为$S$的后缀。
前缀 对任意 $j∈[0, m - 2]$，$S[0 ,j]$为$S$的前缀。
KMP考察了P本身的特征，存储到一个next数组中。
$next(q) = max{k-1 : k < q \text{ and } P[0, k] \text{ is a suffix of } P[0, q]}$
next[q]存储的值为最长相同前缀后缀的长度k-1。
| q | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| P[q] | a | b | a | b | a | b | a | b | c | a |
| next[q] | -1 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | -1 | 0 |
例，ababa的前缀有a，ab，aba，abab；后缀有a，ba，aba，baba。显然最长相同前缀后缀为aba，长度k为3，next数组值为2。
当字符串匹配时，我们不需要再一个一个遍历，P可以大幅向前移动。
假设当前匹配到模式串j位置时失配，KMP算法使用next[j]+1更新j的值。
移动位数 = (已匹配的字符数-1) - 匹配部分最后一位next值 = j - next[j] -1
例，
bacbabababababacambabacaddababacasdsd
ababababca
ababababca
移动位数 = 7 - 5 = 2，此时将P向后移动2位，继续匹配。
KMP伪代码
q := −1;
for i:= 0 to n − 1 do:
while q ≥ 0 and P[q + 1] != T[i] { q := next(q) }; //下一位匹配失败，迭代q去查询next
if P[q + 1] = T[i] { q := q + 1 };
if q = m − 1 { output i − m + 1; q := next(q) };
计算next数组
| q | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| P[q] | a | b | a | b | a | b | a | b | c | a |
| next[q] | -1 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | -1 | ? |
如上表，假设此时我们已经计算了[0-8]位的值，现在我们计算第9位的值，我们可以轻易的从前一位q=8来计算。
此时next[8] = -1，即不存在相同的前后缀，那么next[9]即便存在相同的前后缀，最长也不超过1，检查q[0]与q[9]，若相同，则next[9]=1。
同理，来看另一个例子。
| q | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| P[q] | a | b | a | b | a | b | a | b |
| next[q] | -1 | -1 | 0 | 1 | 2 | 3 | 4 | ? |
假设我们计算了[0-5]的next值，现在需要计算第7位。
next[6]=4，因此next[7]最大不超过5，只要检查q[4+1]与q[7]是否相等，若相等则next[7] = next[6] + 1；若不相等，我们可以检查第二长的前缀的后一位。
第二长的前缀，是最长的前缀的一个最长前缀，即next[6] = 4，next[4] = 2，检查q[2+1]是否等于next[7]，若相等，则next[7] = 2 + 1；若不相等，继续检查第三长的前缀的后一位。
计算next数组伪代码
next(0):= −1; k := −1; q := 1;
while q ≤ m − 1 {
while k ≥ 0 and P[k + 1] != P[q] { k := next(k) }
if P[k + 1] = P[q] { k := k + 1 }
next(q) := k
q := q + 1
}