高效字符串匹配算法KMP详解与学习笔记

时间：11-13 名人轶事提交错误

2. 暴力匹配算法

简单来说，就是一个词的比较，不管是谁写的，永远都是这样。重点是这句话

如果当前字符匹配成功（即S[i]==P[j]），则i++、j++继续匹配下一个字符。如果存在不匹配（即S[i]！=P[j]），则令i=i - (j - 1), j=0。相当于每次匹配失败，i返回，j设置为0.相当于回溯m次，每次最多比较n次。时间复杂度为O(mn)。 KMP使用少回溯使时间复杂度为O(m+n)。

3. KMP算法

3.1 定义

一个基本事实是，当空格与D 不匹配时，您实际上已经知道前六个字符是“ABCDAB”。 KMP算法的思想就是尽量利用这个已知的信息，不把‘搜索位置’移回到已经比较过的位置，而是继续向后移动，从而提高效率。

3.2 步骤

next数组实际上是根据前缀和后缀的最长公共元素推导出来的。该数组表示当该位不匹配时（即next[i] ），模式字符串指针应该调整到哪一位，当该值为-1 时，表示目标字符串指针需要向后移动，模式字符串指针回到0。

3.3 通过代码递推计算next 数组

void GetNext(char* p,int next[])

{

int pLen=strlen(p);

下一个[0]=-1;

整数k=-1；

整数j=0;

而(j pLen - 1)

{

//p[k]代表前缀，p[j]代表后缀

if (k==-1 || p[j]==p[k])

{

++k；

++j；

下一个[j]=k;

}

别的

{

k=下一个[k]；

}

}问题的关键应该是如何用代码来查找下一个数组。显然这里使用了类似于统计归纳的证明方法。 f(n) 可以从f(n-1) 推导出来。关键是这句话

如果p[i]==p[j]，则next[i + 1]=next[i] + 1=j + 1； if p[i] p[j]，如果此时p[ next[j ] ]==p[i]，则next[i + 1]=next[j] + 1，否则继续递归前缀索引j=next[j]，然后重复这个过程。这里最好拍张照片更清楚。

假设i和j的位置如上图所示，通过next[i]=j得到。即对于位置i，段[0，i-1]的最长相同真后缀分别为[0，j-1。 ]和[i - j, i - 1]，即这两段内容是相同的。

根据算法流程，if (P[i]==P[j]), then i++; j++;下一个[i]=j;相当于获取next[i+1]的值。

如果不相等，则j=next[j]，参见下图1/2/3：图1next[j]表示[0, j - 1]段中最长的相同真实后缀的长度。如图所示，左边的两个椭圆用来表示最长相同的真实后缀，即两个椭圆所代表的部分内容相同；同样，右侧也有两个相同的椭圆。因此else语句使用第一个椭圆和第四个椭圆的相同内容来加速获得[0, i - 1]部分相同的真实后缀长度。图2

图3 这张图需要分成左右两半来查看。

4. KMP算法的优化

这部分优化优化了p[j]=p[next[j]]的问题。当p[j] !=s[i] 时，下一个匹配必须是p[ next [j]] 匹配s[i]。如果p[j]=p[ next[j] ]，则必然导致下一步Match失败。如果出现p[j]=p[next[j]]，则需要再次递归，即next[j]=next[next[j]]，从而得到完整的KMP算法。

//优化next数组计算方法

void GetNextval(char* p, int next[])

{

int pLen=strlen(p);

下一个[0]=-1;

整数k=-1；

整数j=0;

而(j pLen - 1)

{

//p[k]代表前缀，p[j]代表后缀

if (k==-1 || p[j]==p[k])

{

++j；

++k；

//与之前的next数组计算相比，变化在以下4行

if (p[j] !=p[k])

下一个[j]=k; //之前只有这一行

别的

//因为p[j]=p[next[j]]不能出现，所以出现时需要继续递归，k=next[k]=next[next[k]]

下一个[j]=下一个[k];

}

别的

{

k=下一个[k]；

}

5. BM算法

KMP从模式字符串的开头开始匹配，1977年，德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了一种新的字符串匹配算法：Boyer-Moore"s算法，简称BM算法。该算法从模式字符串的末尾开始匹配，最坏情况的时间复杂度为O(N)。在实践中，BM算法不仅效率高，而且构思巧妙、易于理解。

BM算法定义了两个规则：坏字符规则：当文本字符串中的字符与模式字符串中的字符不匹配时，我们将文本字符串中不匹配的字符称为坏字符。这时候就需要将模式串向右移动。位数=模式字符串中错误字符的位置- 模式字符串中错误字符的最右边位置。另外，如果模式串中不包含“坏字符”，则最右边的出现位置为-1。

好后缀规则：字符不匹配时，向后移动的次数=好后缀在模式串中的位置- 好后缀最后一次出现在模式串中的位置，如果好后缀在模式串中不再出现模式字符串，它是-1 。

每次后移这两个规则之中的较大值。这两个规则的移动位数，只与模式串有关，与原文本串无关。下面的例子说明了BM算法。例如，给定文本字符串“HERE IS A SIMPLE Examples”和模式字符串“EXAMPLE”，您想要查明模式字符串是否在文本字符串中。如果存在，则返回模式字符串在文本字符串中的位置。

首先，‘文本串’与‘模式串’头部对齐，从尾部开始比较。 “S”与“E”不匹配。此时，‘S’被称为‘坏字符’，即不匹配字符，它对应于模式串的第6位。并且模式串"EXAMPLE"中不包含"S"（相当于最右边出现的位置为-1），这意味着模式串可以向后移动6-(-1)=7位，直接移动到"S" 最后一位数字。还是从最后比较，发现‘P’和‘E’不匹配，所以‘P’是‘坏字符’。然而，“P”包含在模式字符串“EXAMPLE”中。因为“坏字符”“P”对应的是模式串的第6个位置（从0开始编号），而模式串中最右边出现的位置是4，所以模式串向后移动了6-4=2位，两个"P" 对齐。依次比较，得到“MPLE”匹配，这些匹配被称为‘好后缀’（good suffix），即末尾的所有匹配字符串。请注意，“MPLE”、“PLE”、“LE”和“E”都是很好的后缀。发现“我”与“A”不匹配：“我”是一个坏角色。如果是基于坏字符规则，则模式字符串应向后移动2-(-1)=3 位。那么问题来了，有没有更好的方法来移动它呢？更好的移位方法是使用好后缀规则：当字符不匹配时，向后移位的次数=好后缀在模式串中的位置-好后缀最后出现在模式串中的位置，并且如果好的后缀在模式串中没有再次出现，则为-1。所有的“好后缀”（MPLE、PLE、LE、E）之中，只有“E”在“EXAMPLE”的头部出现，所以后移6-0=6位。可以看出，“坏字符规则”只能移位3位，“好后缀规则”可以移位6位。每次将两个规则中较大的值向后移动。这两条规则的移位位数只与模式串有关，与原文串无关。

从最后继续比较，“P”与“E”不匹配，所以“P”是“坏字符”，根据“坏字符规则”，它向后移动6 - 4=2位。因为它是最后一位数字，所以不匹配，尚未收到好的后缀。

（彩蛋）BMH算法——省去好后缀表的优化算法

BMH 不再像BM 算法那样关注不匹配的字符（好的后缀）。它关注坏字符，并根据该字符在模式串P中最后出现的位置计算偏移长度。否则偏移模式串的长度。

研究表明，不好的字符表在匹配过程中起主导作用的概率为94.03%（其实想想就知道），这比使用好的后缀表要高得多。同时后缀表的计算过程也相对复杂。 BMH算法通过减少比较次数来提高BM算法的性能。

字符X不在模板P中，则跳跃步数为模板P的长度。如果字符X在模板P中，则跳跃步数为字符之间的距离=1005；

int 移位[最大数量];

int BMH(常量字符串T, 常量字符串P) {

int n=T.length();

int m=P.length();

//默认值，主字符串左移m位

for(int i=0; i maxNum; i++) {

移位[i]=m；

}

//模式串P中出现的每个字母的最后一个下标，除了最后一个字母

//主字符串永远不会匹配最后一个字符，即需要左移的位数

for(int i=0; i m - 1; i++) {

移位[P[i]]=m - i - 1;

}

//模式字符串在主字符串中的起始位置在哪里？

整数s=0;

//变量从后到前匹配

整数j;

而（s=n - m）{

j=m-1；

//从模式字符串末尾开始匹配

while(T[s + j]==P[j]) {

j——；

//匹配成功

如果（j 0）{

返回s；

}

//查找错误字符（当前与模式字符串匹配的最后一个字符）

//出现在模式字符串的最后位置（最后一位数字除外）

//从模式串末尾移动到该位置所需的步数

s=s + 移位[T[s + m - 1]];

}

返回-1；

}

6. Sunday算法(直接复制过来的)

上面我们介绍了KMP算法和BM算法。两种算法在最坏情况下的搜索时间都是线性的。但实际上，KMP 算法并不比最简单的C 库函数strstr() 快多少，而且虽然BM 算法通常比KMP 算法快，但BM 算法并不是现有字符串搜索算法中最快的算法。本文最后介绍一种比BM算法更快的搜索算法——Sunday算法。

Sunday算法是Daniel M. Sunday在1990年提出的，它的思想与BM算法非常相似：

只是Sunday算法是从前往后匹配的。当匹配失败时，它会关注参与匹配的文本字符串中最后一个字符旁边的字符。

如果该字符没有出现在模式串中，则直接跳过，即移位位数=匹配字符串长度+1；

否则，移位位数=模式字符串中最右边的字符到末尾的距离+ 1。

下面通过一个例子来说明Sunday算法。假设现在您想要在文本字符串“子字符串搜索算法”中查找模式字符串“搜索”。

最初，将模式字符串与文本字符串的左侧对齐：

sub s ring 搜索算法

sea r c h 结果是在第二个字符处发现不匹配。当出现不匹配时，重点关注参与匹配的文本字符串中最后一个字符的下一个字符，即粗体字符i，因为模式字符串搜索没有匹配到i，所以模式字符串直接跳过一大片区域，向右移动位数=匹配字符串长度+1=6+1=7，从i后面的字符（即字符n）开始下一步匹配，如下图： substring _ s e arching 算法

s电子邮箱

结果，第一个字符不匹配。查看文本字符串中最后一个匹配字符旁边的字符。它是“r”，出现在模式字符串中倒数第三个位置，因此模式字符串向右移动。移动3 位（从r 到模式串末尾的距离+ 1=2 + 1=3）以对齐两个"r"，如下所示：

子串s e arch ing 算法

s e arc h