KMP模式匹配

àì夳堔傛蜴生んèń 2022-04-18 05:04 173阅读 0赞

##### KMP算法，能够在线性时间内判定字符串A\[1~N\]是否为字符串B\[1~M\]的子串，并求出A在B中各次出现位置。 #####

首先最朴实的做法是O(NM)的，其次这个问题使用字符串Hash也能在线性时间内求解。  
KMP算法能更高效、准确地处理这个问题，并提供一些额外的信息。详细的讲，KMP算法分为两步：（为方便讨论，以下部分将字符串存储在S\[1…n\]，而不是S\[0…n-1\]）

1.  对字符串A进行自我匹配，求出next数组，表示“A中以i结尾的非前缀子串”与“A的前缀”能够匹配的最长长度，即：  
     n e x t \[ i \] = m a x \{ j \} ， 其 中 j < i 并 且 A \[ i − j + 1... i \] = A \[ 1... j \] next\[i\]=max\\\{j\\\}，其中j<i并且A\[i-j+1...i\]=A\[1...j\] next\[i\]=max\{ j\}，其中j<i并且A\[i−j\+1...i\]=A\[1...j\]  
    特别的，当不存在这样的j时，next\[i\]=0。
2.  对字符串A与B进行匹配，求出一个数组 f f f，其中 f \[ i \] f\[i\] f\[i\]表示“B中以i结尾的子串”与“A的前缀”能够匹配的最长长度，即：  
     f \[ i \] = m a x \{ j \} ， 其 中 j ≤ i 并 且 B \[ i − j + 1... i \] = A \[ 1... j \] f\[i\]=max\\\{j\\\}，其中j\\le i并且B\[i-j+1...i\]=A\[1...j\] f\[i\]=max\{ j\}，其中j≤i并且B\[i−j\+1...i\]=A\[1...j\]

##### 下面讨论next数组的计算方法。 #####

朴素的做法复杂度是 O ( N 2 ) O(N^2) O(N2)的，这里就不做赘述了。我们考虑能否更快地求出next数组。

##### 引理 #####

若 j 0 j\_0 j0是 n e x t \[ i \] next\[i\] next\[i\]的一个“候选项”，即 j 0 < i 且 A \[ i − j 0 + 1... i \] = A \[ 1... j 0 \] j\_0<i且A\[i-j\_0+1...i\]=A\[1...j\_0\] j0<i且A\[i−j0\+1...i\]=A\[1...j0\]，则小于 j 0 j\_0 j0的最大的 n e x t \[ i \] next\[i\] next\[i\]的“候选项”是 n e x t \[ j 0 \] next\[j\_0\] next\[j0\]。换言之， n e x t \[ j 0 \] + 1... j 0 − 1 next\[j\_0\]+1...j\_0-1 next\[j0\]\+1...j0−1之间的数都不是 n e x t \[ i \] next\[i\] next\[i\]的“候选项”。

> 证明：  
> 反证法。假设存在 n e x t \[ j 0 \] < j 1 < j 0 next\[j\_0\]<j\_1<j\_0 next\[j0\]<j1<j0使得 j 1 为 n e x t \[ i \] 的 “ 候 选 项 ” ， 即 A \[ i − j 1 + 1... i \] = A \[ 1... j 1 \] j\_1为next\[i\]的“候选项”，即A\[i-j\_1+1...i\]=A\[1...j\_1\] j1为next\[i\]的“候选项”，即A\[i−j1\+1...i\]=A\[1...j1\]  
> 那我们分别取 A \[ i − j 0 + 1... i \] 和 A \[ 1... j 0 \] 的 后 j 1 个 字 符 A\[i-j\_0+1...i\]和A\[1...j\_0\]的后j\_1个字符 A\[i−j0\+1...i\]和A\[1...j0\]的后j1个字符，显然也相等，而 n e x t \[ j 0 \] < j 1 next\[j\_0\]<j\_1 next\[j0\]<j1，这与 n e x t \[ j 0 \] 的 最 大 性 矛 盾 next\[j\_0\]的最大性矛盾 next\[j0\]的最大性矛盾。故假设不成立。

**使用优化的算法计算next数组**  
根据引理，当next\[i-1\]计算完毕时，我们即可得知next\[i-1\]的所有“候选项”从大到小依次是 n e x t \[ i − 1 \] , n e x t \[ n e x t \[ i − 1 \] \] , n e x t \[ n e x t \[ n e x t \[ i − 1 \] \] \] . . . next\[i-1\],next\[next\[i-1\]\],next\[next\[next\[i-1\]\]\]... next\[i−1\],next\[next\[i−1\]\],next\[next\[next\[i−1\]\]\]...  
而如果一个整数 j 是 n e x t \[ i \] j是next\[i\] j是next\[i\]的“候选项”，那么 j − 1 显 然 也 必 须 是 n e x t \[ i − 1 \] j-1显然也必须是next\[i-1\] j−1显然也必须是next\[i−1\]的“候选项”( A \[ i − j + 1... i \] = A \[ 1.. j \] 的 前 提 是 A \[ i − j + 1... i − 1 \] = A \[ 1... j − 1 \] A\[i-j+1...i\]=A\[1..j\]的前提是A\[i-j+1...i-1\]=A\[1...j-1\] A\[i−j\+1...i\]=A\[1..j\]的前提是A\[i−j\+1...i−1\]=A\[1...j−1\])  
因此，在计算 n e x t \[ i \] next\[i\] next\[i\]时，只需把 n e x t \[ i − 1 \] + 1 , n e x t \[ n e x t \[ i − 1 \] \] + 1 , n e x t \[ n e x t \[ n e x t \[ i − 1 \] \] \] + 1 , . . . . next\[i-1\]+1,next\[next\[i-1\]\]+1,next\[next\[next\[i-1\]\]\]+1,.... next\[i−1\]\+1,next\[next\[i−1\]\]\+1,next\[next\[next\[i−1\]\]\]\+1,....作为j的候选项即可。因此只要我们依序计算 n e x t \[ 1 \] , n e x t \[ 2 \] , . . . , n e x t \[ n \] next\[1\],next\[2\],...,next\[n\] next\[1\],next\[2\],...,next\[n\]不就变成了一个类似递推的问题了吗。  
**举例说明**  
设A=“abababaac”，假设next\[1~6\]已经求出，按照定义next\[6\]=4。  
接下来A\[7\]=A\[5\]=‘a’，说明该位置可以继续匹配，由next\[6\]=4可知next\[7\]=5就是最优解。  
我们继续考虑next\[8\]。此时， A \[ 8 \] = ′ a ′ ≠ a \[ 6 \] = ′ b ′ A\[8\]=&\#x27;a&\#x27;\\ne a\[6\]=&\#x27;b&\#x27; A\[8\]=′a′̸=a\[6\]=′b′，故不能继续匹配长度从5增长到6。我们只能把匹配长度缩短。按照之前的分析，以 i = 7 i=7 i=7为结尾的匹配长度除了 n e x t \[ 7 \] = 5 next\[7\]=5 next\[7\]=5外，还有 n e x t \[ 5 \] = 3 , n e x t \[ 3 \] = 1 next\[5\]=3,next\[3\]=1 next\[5\]=3,next\[3\]=1和 n e x t \[ 1 \] = 0 next\[1\]=0 next\[1\]=0。我们一次尝试这些候选项是否能够匹配到位置i即可。然而A\[8\]与A\[4\]、A\[2\]都不相等，无法延伸，只有A\[1\]=A\[8\]，所以next\[8\]=1。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlYXJsZXNzeGpkeA_size_16_color_FFFFFF_t_70]

在讨论时间复杂度之前，我们先按照上面的思路写出算法实现  
**KMP算法next数组的求法**

1.  初始化next\[1\]=j=0，假设next\[1~i-1\]已求出，下面求解next\[i\]。
2.  不断尝试扩展匹配长度j，如果扩展失败(下一字符不相等)，领j变为next\[j\]，直至j为0(应该从头开始匹配)。
3.  如果能够扩展，匹配长度j就增加1。next\[i\]的值就是j。

next[1] = 0;
    for (int i = 2, j = 0; i<=n; ++i){ 
    	while (j>0 && a[i]!=a[j+1]) j = next[j];
    	if (a[i] == a[j+1]) ++j;
    	next[i] = j;
    }

因为定义的相似性，求解f数组与求解next数组的过程基本是一样的。

for (int i=1, j=0; i<=m; ++i){ 
    	while (j>0 && (j==n || b[i]!=a[j+1])) j=next[j];
    	if (b[i] == a[j+1]) ++j;
    	f[i] = j;
    	//if (f[i] == n) ,此时就是A在B中的某一次出现
    }

**复杂度分析**  
这就是KMP模式匹配算法。在上面代码的while循环中，j的值不断减小，j=next\[j\]的执行次数不会超过每层for循环开始时j的值与while循环结束时j的值之差。而在每层for循环中，j的值至多增加1。因为j始终非负，所以整个计算过程中，j减小的幅度总和不超过j增加的幅度总和。故j的总变化次数至多为2\*(N+M)。整个算法的时间复杂度为 O ( N + M ) O(N+M) O(N\+M)

本文绝大部分摘抄自《算法竞赛进阶指南》

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlYXJsZXNzeGpkeA_size_16_color_FFFFFF_t_70]: /images/20220418/645e7aa69d1f4c8394e04498559322ca.png