kmp字符串匹配

发表于 分类于 ， 阅读次数：
kmp 是一种极为高效的字符串匹配算法。所谓字符串匹配，即为给定一个需要处理的文本串 s （假设其长度为 n ）和一个需要在文本串中搜索的模式串 p （假设其长度为 m ），查询在该文本串中，给出的模式串的出现有无、次数、位置等。

kmp 是一种极为高效的字符串匹配算法。所谓字符串匹配，即为给定一个需要处理的文本串 s （假设其长度为 n ）和一个需要在文本串中搜索的模式串 p （假设其长度为 m ），查询在该文本串中，给出的模式串的出现有无、次数、位置等。

想要理解 kmp ，需要对字符串匹配的朴素做法有一个更加深入的认识。我们设指向文本串的指针为 $p_1$ ，指向模式串的指针为 $p_2$ 。想要在文本串中搜索模式串，就可以对 $p_1$ 从 $1 - n$ 进行遍历，判断以 $p_i$ 指向元素作为开头的模式串字串是否与文本串相同。其代码可以简单的表示为：

1
2
3
4
5
6
7
8
for(int i = 1; i <= n; i++)
{
	int j = 0;
	while(s[i] == p[++j])
	{
		if(j == m)  ... //匹配成功 
	}
}

显然这种做法的时间复杂度是$O(nm)$的。

那么我们思考：这种朴素做法笨重的地方在哪里？

仔细分析可以发现，朴素做法在以每一轮匹配时，都重新进行了文本串字串和模式串是否相同的验证。也就是说：其上一次字串与模式串匹配的结果被直接丢弃了，并没有得到合理的利用。

从此下手，我们该如何利用这一结果？我们可以手搓几组样例去简单地尝试。不难发现：当算法实际的复杂度接近最坏复杂度$O(nm)$时，恰好是文本串具有很好重复性的时候——这会让可怜的模板串匹配到它最后几位时才发现异常。此时我们的目的就很明确了：我们要去利用、挖掘文本串的循环重复性来跳过一些不必要的运算。 而这，就是 kmp 算法的思想所在。

为了方便理解，我们举个例子：

s：ababa…

p：ababc

很明显，当匹配到第五个字符时，匹配将发生异常。对于朴素做法，此时应将 $p_1 + 1$，进行下一次匹配。但这时我们仔细观察模式串：它的前三项 “aba” 和后三项 “aba” 是一致的！在这里，我们给前三项命名为真前缀，给后三项命名为真后缀，由于匹配在第五位终止，所以有 p[1-3] = 真前缀 ；而又有 真前缀 = 真后缀 ，所以有 p[1-3] = 真后缀。你会惊讶的发现：这个结论可以将匹配进度提升到 $p_1 = 3$, $p_2 = 3$ 的时刻！

这说明，在文本串中，真前缀 = 真后缀 的状态是十分宝贵的。所以在对文本串的预处理中，我们引入了 next[ ] 数组来存储这种状态。next[i] 表示在长度为 i 的文本串中，其长度为 next[i] 的真前缀和真后缀是相等的。例如上面的例子：

s：ababa

其next[ ] 数组值分别为：

next[ ]: 0 0 1 2 3

再例如：

s：abcda

next[ ]：0 0 0 0 1

至此理论层面的内容就介绍完毕了。下面将介绍 kmp 算法的具体实现。

首先是求出 next[ ] 数组。对此我们可以考虑使用双指针的思想来求解：设立 i，j 两个指针，i指针负责遍历文本串，j指针负责记录next[ ]数组，初始时将其放置在文本串0位置。当s[i] = s[j+1] 时，说明对于该长度为 i 的文本串来说，满足真前缀(s[j+1])等于真后缀(s[i])。实现的具体代码为：

1
2
3
4
5
6
7
8
for(int i = 2, j = 0; i <= len2; i++) // 求nxt数组 
{
    while(j > 0 && p[i] != p[j + 1]) // 保证可以再后退 并且 匹配不成功 
        j = nxt[j]; // 后退 
    if(p[i] == p[j + 1])
        j++; // 如果匹配成功，指针右移一位（长度+1） 
    nxt[i] = j;  // 记录下 前缀 = 后缀 的最大长度 
}

同样的道理，对模板串和文本串进行匹配时，可以将模板串指针看成上述过程的 j，然后重走一遍该过程：当 j = m 时，则说明匹配成功。具体代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
for(int i = 1, j = 0; i <= len1; i++) // 求位置 
{
    while(j > 0 && s[i] != p[j + 1]) //同上 
        j = nxt[j];
    if(s[i] == p[j + 1]) //同上 
        j++;
    if(j == len2) // 匹配成功 
    {
        j = nxt[j]; // 此次匹配结束，一定要退回上一个 前缀 = 后缀 的状态，从而开始下一次匹配 
        print(answer); 
    }
}

kmp 的时间复杂度是$O(n + m)$，远远优于朴素做法。

拓展：再谈next[ ]数组

上面说过，kmp的算法思想本质上是运用了文本串内部的循环重复性。对于循环，我们数学上有一个概念叫做循环节；这对于文本串同样具有。

求出文本串循环节的方法同样十分简单。可以证明： 长度为 n 的文本串中，循环节的长度为 n - next[n] ，即为该文本串中前 n - next[n] 个字符。

证明十分简单。我们还是以abababab为例，由于next[8] = 6，即前6个字母组成的子串和后6个字母组成的字串完全相同，有：
s[1] = s[5], s[2] = s[6], s[3] = s[7], s[4] = s[8]。
化简得：
s[1] = s[3] = s[5] = s[7]
s[2] = s[4] = s[6] = s[8]
然后就显然了。