KMP 算法是一种字符串模式匹配算法,它可以实现在 O(n+m)的时间复杂度下完成串的模式匹配。对于刚刚接触KMP 算法的人来说,一般是都很难理解:为什么KMP 算法可以完成模式匹配,KMP 中的 next 数组又究竟是什么?
下面我将简单讲解一下我个人对KMP 算法的的理解,以及数学证明。
KMP 算法的简单理解
首先假设KMP 算法中,用 S 来表示主串,用 i 遍历主串;用 T 来表示待匹配的串,用 j 遍历待匹配串。然后在 KMP 算法匹配过程中 i 是一直递增而无需回溯的。
现在假设有一个主串 S:
一个待匹配的串 T:
要求找到串 T 在主串 S 中第一次出现的地方,下面使用 KMP 算法的核心思想进行模拟匹配:
- (1)从主串 S 和串 T 的开头开始匹配,假设 S0——S4 = T0——T4,此时匹配到了 S5 和 T5 位置,并且 S5≠T5;
- (2)我们希望 S 的索引 i 不回溯,那么我们可以通过移动 T 的索引 j ,使得 T 相对 S 往右移动,使得 j 之前的 T 的子串与 S 匹配,并且希望移动的距离最小;
- (3)假设当 j 移动到 T3 位置时,T3 之前的子串 T0——T2 = S2——S4;
- (4)然后再判断 S5 与 T3 是否匹配,如果匹配,i 和 j 同时递增,继续匹配余下的;如果不匹配,则重复以上步骤;
由上面可以看出,KMP 算法的核心在于步骤(2)(3),串 T 的 j 究竟要回溯多少的距离。下面来分析一下:
从步骤(1)知道 S2 S3 S4 = T2 T3 T4
从步骤(3)知道 S2 S3 S4 = T0 T1 T2
因此 T0 T1 T2 = T2 T3 T4
发现了没有,T0 T1 T2 是串 T0 T1 T2 T3 T4 的前缀,T2 T3 T4 则是其后缀,前缀与后缀相等。
也就是说,如果我们能找到前缀和后缀最长交集,也就知道了 j 究竟要回溯到什么位置。
步骤(2)的图
就步骤(2)而言,T5 之前的子串 T0 T1 T2 T3 T4 的
前缀集合为{T0、T0 T1、T0 T1 T2、T0 T1 T2 T3};
其后缀集合为{T4、T3 T4、T2 T3 T4、T1 T2 T3 T4};
假设 T0 T1 T2 T3 ≠ T1 T2 T3 T4 且 T0 T1 T2 = T2 T3 T4
那么子串 T0 T1 T2 T3 T4 前缀和后缀最长交集的长度即为 3。
所以在步骤(3)中,j 应当移动到 T3 位置,使得 j 之前的子串即为上面所求的最大交集 T0 T1 T2。
而 KMP 算法中的 next 数组中的数据正是根据前缀和后缀的最大交集长度所得出,表示的是当 j 位置发生不匹配时的下一个 j 的位置。
比如说,当 j=3 时,发生了不匹配,那么 j 应当移动到 next[3]的位置(也就是令 j=next[3])。
求 next 数组算法代码实现
下面代码中的数组的第 0 个元素都是用来表示串的长度,而并不表示串的第一个元素。
代码实现并不唯一,next 数组的值也并不唯一,因情况而定。
比如说,如果数组的第 0 个元素不用来表示串的长度,而是表示串的第一个元素,那么 next 数组的值的求法也会有所改变。
//KMP 算法中的 next 数组求法示例代码
void find_next(char T[], int next[])
{
i=1;
next[1]=0;//next[1]=0 表示当前已经没有元素与主串中的匹配了
j=0;
while(i<=T[0])
{
if(j==0 || T[i]==T[j])
{
++i;
++j;
next[i]=j;
}
else
j=next[j];
}
}