KMP查找子字符串

KMP查找子字符串

前言  

  KMP 算法是一种改进的字符串匹配算法,由 D.E.Knuth,J.H.Morris 和 V.R.Pratt 同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称 KMP 算法)。KMP 算法的关键是利用匹配失败后的信息(已经匹配的部分中的对称信息),尽量减少模式串(待搜索词)与文本串的匹配次数以达到快速匹配的目的。具体实现就是实现一个 next() 函数,该函数本身包含了模式串的局部匹配信息。

一,kmp 算法的原理:

字符串匹配是计算机的基本任务之一。它所执行的任务就是在一个文本(较长的字符串)中查找是否包含着当前指定的模式字符串(较短的字符串),并找到其位置,这就是字符串匹配问题。
注:在算法导论里面待搜索的词叫 “模式” 字符串,并用 P 来表示,本文有的地方叫他“待搜索词”。如无特殊说明数组下标以 0 为起始。
举例来说,有一个长字符串 “BBC ABCDAB ABCDABCDABDE”(即文本串),我想知道里面是否包含另一个模式字符串 “ABCDABD”,它的位置在哪呢?

1,朴素匹配算法过程:

1).

首先,长字符串 “BBC ABCDAB ABCDABCDABDE” 的第一个字符与搜索词 “ABCDABD” 的第一个字符,进行比较。因为 B 与 A 不匹配,所以搜索词后移一位。

2).

因为 B 与 A 不匹配,搜索词再往后移。

3).

就这样,直到长字符串有一个字符,与搜索词的第一个字符相同为止(准备开始位置不变搜索下一个字符)。

4).

接着比较字符串和搜索词的下一个字符,还是相同。

5).

但是后面的有可能是不完全匹配的,这时在长字符串中遇到一个字符与搜索词对应的字符不相同。

6).

最自然的反应是,将搜索词整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把搜索位置 BCD 这一段又要重比一次,然而它的比较在直到了后面有 “AB” 与前面的 “AB” 对称的情况下是可以避免的,直到遇到 “AB” 才萌发新的可能使整个字符匹配的可能性。

2,KMP 匹配算法过程:

1).

接着前面的匹配过程,现在来看:一个基本事实是,当空格与 D 不匹配时,你其实知道前面六个符 “ABCDAB” 已经匹配的部分。KMP 算法的想法是,设法利用这个搜索词的子串(就是搜索词的某个前缀)的已知对称值,注意这里的对称非中心对称,而是基于搜索词的某一个前缀的对称信息,在不匹配的时候跳过一些不必要的位置来加速匹配速度,这样就提高了效率。

2).

怎么做到这一点呢(如何跳过不必要的位置在不匹配时)?可以针对搜索词,算出一张模式字符串的前缀函数表。这张表是如何产生的,后面再介绍,这里只要知道就可以了。

3).

已知空格与 D 不匹配时,前面六个字符 “ABCDAB” 是匹配的。查模式串的《前缀函数表》可知,其前缀(即 ABCDAB)中的最后一个匹配字符 B 的位置对应的 “部分匹配值” 为 2,因此按照下面的公式算出向后移动的位数(直接将前面的对称信息调到后面的对称位置,跳过一些不必要的位置):

移动位数 = 已匹配的字符数 - 当前已匹配字符串的部分匹配值

因为 6 - 2 等于 4,所以将搜索词向后移动 4 位(之所以移动 4,是因为搜索词的已匹配的前缀串 “ABCDAB” 的部分匹配值为 2,即有 “AB” 对称,因为当前已匹配字符串的 “AB” 始终要找到下一个 “AB” 的开始位置,而这个开始位置恰好就在本字符串中的后缀中,所以直接移动 4,我们可以最大减少匹配次数)。

4).

因为空格与C不匹配,搜索词还要继续往后移。这时,已匹配的字符数为 2(”AB”),对应的 “部分匹配值” 为 0。所以,移动位数 = 2 - 0,结果为 2,于是将搜索词向后移 2 位。

5).

因为空格与 A 不匹配,继续后移一位。

6).

逐位比较,直到发现 C 与 D 不匹配。于是,移动位数 = 6 - 2,继续将搜索词向后移动 4 位。

7).

逐位比较,直到搜索词的最后一位,发现完全匹配,于是搜索完成。如果还要继续搜索(即找出全部匹配),移动位数 = 7 - 0,再将搜索词向后移动 7 位,这里就不再重复了。

3, 关于前缀函数表

1)前缀和后缀

首先,要了解两个概念:”前缀” 和 “后缀”。 “前缀” 指除了最后一个字符以外,一个字符串的全部头部组合;”后缀” 指除了第一个字符以外,一个字符串的全部尾部组合。

2). 前缀函数表的产生

“前缀函数” 的对称值(也叫部分匹配值)就是模式串的对应前缀中的 “前缀” 和 “后缀” 的最长的共有元素的长度(实质是最大对称程度)。以 “ABCDABD” 为例,

  • “A” 的前缀和后缀都为空集,共有元素的长度为 0;
  • “AB” 的前缀为 [A],后缀为 [B],共有元素的长度为 0;
  • “ABC” 的前缀为 [A, AB],后缀为 [BC, C],共有元素的长度 0;
  • “ABCD” 的前缀为 [A, AB, ABC],后缀为 [BCD, CD, D],共有元素的长度为 0;
  • “ABCDA” 的前缀为 [A, AB, ABC, ABCD],后缀为 [BCDA, CDA, DA, A],共有元素为 “A”,长度为 1;
  • “ABCDAB” 的前缀为 [A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为 “AB”,长度为 2(“AB” 是其最大对称串,长度为 2);
  • “ABCDABD” 的前缀为 [A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为 [BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为 0。

3). 前缀函数表的意义

A, 首相要搞清楚的是它是模式字符串的所有前缀产生的一张表,保存的值表征了最大对称度,我们一般用 next 数组来保存其某个前缀的对称值,例如 next[6]=2,代表的就是模式串的某个有 6 个字符的前缀 “ABCDAB”,这个前缀的对称度就是 2,即“AB” 是对称的。

B, 模式串的某前缀的对称值的实质是,有时候,搜索词已经部分匹配了(一定是某个前缀),其某个前缀(已经匹配部分)的头部和尾部会有重复。比如,”ABCDAB” 之中前缀有 “AB”,后缀也有 “AB”,那么它的 “前缀函数对称值” 就是 2(”AB” 的长度, 且 “AB” 是 “ABCDAB” 所有前缀和后缀中的最长公有元素)。搜索词移动的时候,第一个 “AB” 向后移动 4 位(字符串长度 - 部分匹配值),就可以来到第二个 “AB” 的位置,在这个新的位置我们跳过了不必要的比较位置,并且直接就有 “AB” 匹配。

二,前缀函数表实现原理

  通过上文完全可以对 kmp 算法的原理有个清晰的了解,那么下一步就是编程实现了,其中最重要的就是如何根据待匹配的模式字符串求出其所有前缀函数表中的最大对称值,在下文中我们将其存储在 next 数组中。

1,编程策略:

1)、当前字符的前面所有字符的对称程度为 0 的时候,只要将当前字符与前面这个子串的第一个字符进行比较。这个很好理解啊,前面所有字符串的对称值都是 0,说明都不对称了,如果多加了一个字符,要对称的话只能是当前字符和前面字符串的第一个字符对称。比如 “ABCDA” 这个里面 “ABCD” 的最大对称值是 0,那么后面的 A 的对称程度只需要看它是不是等于前面字符串的第一个字符 A 相等,如果相等就增加 1,如果不相等那就保持不变,显然还是为 0。

2)、按照这个推理,我们就可以总结一个规律,不仅前面是 0 呀,如果前面字符串的的最大对称值是 1(k),那么我们就把当前字符与前面字符串的第二(k)个字符即 P[1](P[k])进行比较,因为前面的是 1(k),说明前面的字符已经和第一(k)个字符相等了,如果这个又与第二(k+1)个相等了,说明对称程度就是 2(k+1)了。有两(k+1)个字符对称了。比如上面 “ABCDA” 的最大对称值是 1,说明它只和第一个 A 对称了,接着我们就把下一个字符 “B” 与 P[1](即第二个字符)比较,又相等,自然对称程度就累加了,就是 2 了。

但是如果不相等呢?那么这个对称值显然要减少,并且我们只能到前面去寻找对称值,而在找的过程我们同时也利用前缀函数表快速搜索找到与当前字符匹配的位置。比如假设是 “(AGCTAGC)(AGCTAGC)T”(请无视字符串中的括号,只为方便看出对称),

模式字符串:AGCTAGCAGCTAGCT
模式字符串的前缀函数表:
000012312345674

显然最后一个 T 的前一个位置的对称度是 7, 说明 T 的前一个位置的 7 个字符的后缀必与 7 个字符的前缀相等,然而 T!=P[7],说明 T 位置的对称度只能是比 7 小的长度的前缀,所以递减 k 值,递减为多少呢?那么我们应该利用已经得到的 next[0]···next[k-1] 来求 P[0]···P[k-1] 这个前缀中最大相同前后缀, 当前字符前一个位置的对称度为 k=next[13]=7,显然必须以 7 为基准减少,即在前缀长度为 7 以内的范围重新寻找以 T 结尾的前缀,所以 k=next[6] (即下面参考代码中的k = next[k-1];),再接着判断是否相等

3)、按照上面的推理,我们总是在找当前字符 P[q](q 为遍历到的位置下标,见下面程序)通过其前一个位置的对称值判断是否与 P[k] 相等,如果相等,那么加,如果不相等,那么就减少 k 值,重新寻找与与 P[q] 相等的元素位置

2,参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void MakeNext(const char P[],int next[])
{
int k;//k:最大对称长度
int m = strlen(P);//模版字符串长度
next[0] = 0;//模版字符串的第一个字符的最大对称值必为0
for (int q = 1,k = 0; q < m; ++q)//for循环,从第二个字符开始,依次计算每一个字符对应的next值
{//在前一个位置的k不为0,但是却不相等,那么减少k,重新寻找与P[q]相等的位置,让下面的if来增加k
while(k > 0 && P[q] != P[k])//
k = next[k-1]; //while循环是整段代码的精髓所在,
if (P[q] == P[k])//如果相等,那么最大相同前后缀长度加1
k++;//增加k的唯一方式
next[q] = k;
}
}

附完整代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include "vector"
#include "string"
#include <iostream>
#include "algorithm"

using namespace std;

//计算模式P的部分匹配值,保存在next数组中
void MakeNext(const string &P, vector<int> &next)
{
int q, k;//k记录所有前缀的对称值
int m = P.size();//模式字符串的长度
next[0] = 0;//首字符的对称值肯定为0
for (q = 1, k = 0; q < m; ++q)//计算每一个位置的对称值
{
//k总是用来记录上一个前缀的最大对称值
while (k > 0 && P[q] != P[k])
//k = next[k - 1];//k将循环递减,值得注意的是next[k]<k总是成立
--k;
if (P[q] == P[k])
k++;//增加k的唯一方法
next[q] = k;//获取最终值
}
}


void KmpMatch(const string &T, const string &P, vector<int> &next)
{
int n, m;
n = T.size();
m = P.size();
MakeNext(P, next);
for (int i = 0, q = 0; i < n; ++i)
{
while (q > 0 && P[q] != T[i])
q = next[q - 1];
if (P[q] == T[i])
q++;
if (q == m)
{
cout << "模式文本的偏移为:" << (i - m + 1) << endl;
q = next[q - 1];//寻找下一个匹配
}
}
}

int main()
{
system("color 0A");
vector<int> next(20, 0);//保存待搜索字符串的部分匹配表(所有前缀函数的对称值)
string T = "BBC ABCDAB ABCDABCDABDE";//文本
string P = "ABCDABD";//待搜索字符串
cout << "文本字符串:" << T << endl;
cout << "模式字符串:" << P << endl;
KmpMatch(T, P, next);
cout << "模式字符串的前缀函数表:" << endl;
for (int i = 0; i < P.size(); i++)
cout << next[i];
cout << endl;
system("pause");
return 0;
}

参考资源:

【1】网友,c_cloud,《KMP,深入讲解 next 数组的求解》,博客地址,http://www.cnblogs.com/c-cloud/p/3224788.html
【2】网友,yearn520,《KMP 算法的前缀 next 数组最通俗的解释》,博客地址,http://blog.csdn.net/yearn520/article/details/6729426
【3】《算法导论》,第三十二章,字符串匹配
【4】网友,jBoxer,《The Knuth-Morris-Pratt Algorithm in my own words》,博客地址,http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/
【5】九度 OJ,http://ac.jobdu.com/problemset.php?page=2
【6】 https://blog.csdn.net/EbowTang/article/details/49129363