KMP（1）

字符串匹配问题

首先我们先把问题明确一下，给定两个字符串 P [1..P.len] 和 S [1..S.len]，找出 P 在 S 中第一次出现的位置 L，即最小的 L 满足 P [1..len]=S [L..L+len-1]。例如”HA” 在”WAHAHA” 中第一次出现的位置是 3（这一节约定下标都是从 1 开始）

暴力算法

从小到大枚举 L，然后判断 P [1..len]=S [L..L+len-1] 的条件是不是满足；不满足就 + 1 试下一个 L。伪代码如下：

Match(P,S)
    For L = 1...S.len - P.len + 1
        Found = True
        For i = 1...P.len
            If P[i] ! = S[L + i - 1]
                Found = False
                Break
            If Found
                Return L
    Return -1

用一张图来展示暴力匹配的过程：

上图中第一行的字符串是 S，第二行的字符串是 P。同时第 2 行也是枚举 L=1 时的匹配过程，前 5 个字符 abbba 都匹配上了；但是第 6 个字符失配了。第 3~5 行是枚举 L=2, 3, 4 时的匹配过程，都是第一个字符就失配了；第 6 行是 L=5 时的匹配过程，第一个字符 a 匹配上了，第二个字符失配了

KMP 算法

首先我们定义一个函数：失配位置 f (x)。f (x)=k 表示当 L=x 时，失配的字符是 S [k]。注意这个位置是在字符串 S 上的，而不是 P 上的。在上面的例子中，f (1)=6, f (2)=2, f (3)=3, f (4)=4, f (5)=6

KMP 算法的优化思路就是，枚举 L 的过程中，跳过使失配位置减少的 L。例如我 L=1 的时候已经辛辛苦苦匹配上 5 个字符 S [1..5] 了，在第 6 个字符失配，也就是 f (1)=6。那么失配之后能不能至少从 L=5 开始匹配，跳过 L=2..4。因为 L=2..4 时，f (2) f (3) f (4) 都比 f (1) 还小。好歹 f (5) 等于 f (1)，所以从 L=5 开始匹配

跳过使失配位置减少的 L 还有一个好处，就是从 L=x 跳到 L=y 时，其实并不用从 S [y] 开始匹配，而是直接从 S [f (x)] 开始匹配即可

在上图的例子中，L=1 时，在 f (1)=7 失配。这时我们跳到 L=4 继续 (为什么在 L=4 继续，看上面一段文字)，注意继续时我们并不用再比较 P [1] 和 S [4]，P [2] 和 S [5]， P [3] 和 S [6]，而是直接比较 P [4] 和 S [f (1)]（S [f (1)] = S [7]）

如上图所示，如果 L=x 时，P [1..100] 与 S [x..x+99] 匹配上。那么 L=x+1 时，P [1..99] 能与 S [x+1, x+99] 匹配上当且仅当 P [1]=P [2]=P [3]=P [4]=…=P [100]，也就是 P [1..100] 是 aaaa….a 这样类型的

同理，L=x+2 时，P [1..98] 能与 S [x+2 … x+99] 匹配当且仅当 P [1]=P [3]=P [5]…=P [99] 且 P [2]=P [4]=P [6]=…P [100]，也就是 P [1..100] 是 ababab…ababab 这样类型的。再同理，L=x+3 时，P 能匹配到 S [x+99] 的位置当且仅当 P [1..100] 是 abcabcabc…abcabc 这样类型的

用更一般的话说，如果在 L=x 时，P [1..K] 匹配上了 S [x..x+K-1]；那么当 L=x+d 时，P 和 S 匹配的两段是 P [1..K-d] 匹配 S [x+d .. x+K-1]，而 S [x+d .. x+K-1] 又等于 P [1+d..K]（根据 L=x 时的匹配）。所以在 P [K+1] 失配时，KMP 的思路是，找一个最小的 d 满足 P [1..K-d]=P [1+d..K]

形象的说也就是找到 P [1..K] 的一个最长前缀，并且这个前缀同时也是 P [1..K] 的一个后缀，也就是 P [1..K] 的前 j 个字符组成的字符串和后 j 个字符组成的字符串相等

比如 P [1..6]=”aaaaaa”，那么这个（同时也是后缀的）最长前缀是 P [1..5]=”aaaaa”；如果 P [1..6]=”abaaba”，那么这个（同时也是后缀的）最长前缀是 P [1..3]=”aba”；如果 P [1..6]=”ababab”，那么这个（同时也是后缀的）最长前缀是 P [1..4]=”abab”……

如果我们知道 P [1..K] 的（同时也是后缀的）最长前缀是 P [1..j]，我们就记作 next [K]=j。这个 next 数组也叫作 next 函数。对于一个字符串 P 来说，我们可以先手算出对应 next 数组，例如”bababb” 的 next=[0, 0, 1, 2, 3, 1]

有了 next 数组，就意味着我们可以达成 KMP 的优化思路：

当匹配 P [1..K] 与 S [x..x+k-1] 都成功，而 P [K+1] 与 S [x+K] 失配时
通过将 P [next [K]] 对准 S [x+k-1]，实现跳过使失配位置减少的 L
继续比较 P [next [K]+1] 与 S [x+K]，而不用从 P [1] 开始比较

有了 next 数组，KMP 匹配的伪代码是这样的。注意我们特别让 next [0]=-1：

j = 0
For i = 1...S.len
{
    //这时p[j]与S[i-1]是匹配上的，尝试匹配P[j+1]与S[i]
    while(j >= 0 && S[i] != P[j + 1])
        j = next[j]
    j = j + 1
    if(j == P.len)
        return i - P.len + 1
}

用图示来展示 KMP 的过程（已知 next 数组）：

上图从第三行开始匹配，注意是 P [j+1] 匹配 S [i]，所以一开始 S [1..5] 匹配上 P [1..5]。这时 i=6，j=5 开始尝试匹配 S [6] 和 P [6]，匹配失败，j = next [j]=next [5]=3

于是第 4 行尝试匹配 S [6] 和 P [j+1]=P [4]，成功。之后一直成功匹配到 S [7] 和 P [5]。这时 S [8] 和 P [6] 匹配失败，j = next [j]=next [5]=3

于是第 5 行尝试匹配 S [8] 和 P [4]，失败。j = next [j]=next [3]=1。于是第 6 行尝试匹配 S [8] 和 P [2]，失败。j = next [j]=next [1]=0。于是第 7 行尝试匹配 S [8] 和 P [1]，失败。j = next [j]=next [0]=-1。这时 j=-1 会跳出 while 循环，j++ 使得 j=0。然后进行下一次 i=9 的循环

于是第 8 行 i=9, j = 0，尝试匹配 S [9] 和 P [1]，成功。之后一直成功匹配到 S [13] 和 P [5]。这时 S [14 和 S [6] 匹配失败，j = next [j]=next [5]=3

于是第 9 行，S [14] 匹配 P [4] 成功，S [15] 匹配 P [5] 成功，S [16] 匹配 P [6] 失败，j = next [j]=next [5]=3。于是第 10 行，S [16] 匹配 P [4] 成功，S [17] 匹配 P [5] 成功，S [18] 匹配 P [6] 成功，这时找到了一个完成的匹配

假设已知 next 数组，KMP 算法的复杂度显然就是 O (i 变化的总量 + j 变化的总量)，其中 i 是从 1~S.len，显然一共变换 O (S.len) 次。J 会通过 j=j+1 变大，也会通过 j=next [j] 变小。不过 j 变大的次数与 i 循环次数一样都是 O (S.len) 次，而每次 j 变小最小变到 - 1。所以 j 减小的总量最多是 S.len+1，也是 O (S.len)