KMP算法详解 --- 彻头彻尾理解KMP算法

阅读量：6262 次

发布时间：2019-06-22

本文共 5444 字，大约阅读时间需要 18 分钟。

前言　　

　　之前对kmp算法虽然了解它的原理，即求出P₀···P_i的最大相同前后缀长度k。

　　但是问题在于如何求出这个最大前后缀长度呢？

　　我觉得网上很多帖子都说的不是很清楚，总感觉没有把那层纸戳破，

　　后来翻看算法导论32章字符串匹配，虽然讲到了对前后缀计算的正确性，但是大量的推理证明不大好理解，没有与程序结合起来讲。

　　今天我在这里讲一讲我的一些理解，希望大家多多指教，如果有不清楚的或错误的请给我留言。

1.kmp算法的原理：

　　部分内容转自：

是计算机的基本任务之一。

举例来说，有一个字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一个字符串"ABCDABD"？

许多算法可以完成这个任务，（简称KMP）是最常用的之一。它以三个发明者命名，起头的那个K就是著名科学家Donald Knuth。

这种算法不太容易理解，网上有很多，但读起来都很费劲。直到读到的文章，我才真正理解这种算法。下面，我用自己的语言，试图写一篇比较好懂的KMP算法解释。

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

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

就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。

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

直到字符串有一个字符，与搜索词对应的字符不相同为止。

这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。

一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。

怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。

已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数：

　　移动位数 = 已匹配的字符数 - 对应的部分匹配值

因为 6 - 2 等于4，所以将搜索词向后移动4位。

10.

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

11.

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

12.

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

13.

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

14.

下面介绍《部分匹配表》是如何产生的。

首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。

15.

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"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；

　　－　"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

16.

"部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，"ABCDAB"之中有两个"AB"，那么它的"部分匹配值"就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置。

2.next数组的求解思路

　　通过上文完全可以对kmp算法的原理有个清晰的了解，那么下一步就是编程实现了，其中最重要的就是如何根据待匹配的模版字符串求出对应每一位的最大相同前后缀的长度。

int
Next
[
1000
];
void
getNext( 
char
* s) 
{ 
Next
[
0
]
=
0; 
// 模式串第一个字符的最大前后缀长度为0
int
i
,
k
,
len
=
strlen(s); 
for( 
i
=
1
,
k
=
0; 
i
<
len; 
++
i) 
// 第二个字符开始，依次计算每一个字符对应的next值
{ 
while(s 
[
i
]
!=s 
[
k
]
&&
k
>
0) 
//递归的求出s[0]···s[q]最大相同的前后缀长度k
k
=
Next
[
k
-
1
];
//之所以-1是因为s串的下标是从0开始而不是从1开始
if(s 
[
i
]
==s 
[
k
])
++
k; 
Next
[
i
]
=
k; 
}
}

　　现在我着重讲解一下while循环所做的工作：

　　已知前一步计算时最大相同的前后缀长度为k（k>0），即P[0]···P[k-1]；(k-1的原因)

　　此时比较第k项P[k]与P[q],如图1所示

　　如果P[K]等于P[q]，那么很简单跳出while循环;

关键！如果不等呢？？？
- 那么我们应该利用已经得到的next[0]···next[k-1]来求P[0]···P[k-1]这个子串中最大相同前后缀，可能有同学要问了——为什么要求P[0]···P[k-1]的最大相同前后缀呢？？？是啊！为什么呢？原因在于P[k]已经和P[q]失配了，而且P[q-k] ··· P[q-1]又与P[0] ···P[k-1]相同，看来P[0]···P[k-1]这么长的子串是用不了了，那么我要找个同样也是P[0]打头、P[k-1]结尾的子串即P[0]···P[j-1](j==next[k-1])，看看它的下一项P[j]是否能和P[q]匹配。如图2所示

#include<iostream>
#include<cstring>
using
namespace
std; 
int
Next
[
1000
];
void
getNext( 
char
* s) 
{ 
Next
[
0
]
=
0; 
int
i
,
k
,
len
=
strlen(s); 
for( 
i
=
1
,
k
=
0; 
i
<
len; 
++
i) 
{ 
while(s 
[
i
]
!=s 
[
k
]
&&
k
>
0) 
k
=
Next
[
k
-
1
];
if(s 
[
i
]
==s 
[
k
])
++
k; 
Next
[
i
]
=
k; 
}
}
int
kmp( 
char
*
s1
,
char
*
s2) 
{ 
getNext( 
s2); 
int
i
,
k
,
l1
=
strlen( 
s1
),
l2
=
strlen( 
s2
),
cnt
=
0; 
for( 
i
=
0
,
k
=
0; 
i
<
l1; 
++
i) 
{ 
while( 
s1
[
i
]
!=
s2
[
k
]
&&
k
>
0) 
k
=
Next
[
k
-
1
];
if( 
s1
[
i
]
==
s2
[
k
])
++
k; 
if( 
k
==
l2) 
{ 
++
cnt; 
k
=
Next
[
k
-
1
];
}
}
return
cnt; 
}
char
s1
[
1000
],
s2
[
1000
];
int
main() 
{ 
ios_base
::
sync_with_stdio( 
false); 
cin
.
tie( 
0); 
while( 
cin
>>
s1
>>
s2) 
{ 
cout
<<
kmp( 
s1
,
s2) 
<<
endl; 
}
return
0; 
}
/*
*/

其实我们可以发现KMP算法的精华部分是一个DP，每次右滑时，都是根据前面状态得到的有用信息进行的。相当于记忆化更新。这样算法才具有了很高的效率。

3.kmp的优化

KMP算法的原理就是利用相匹配的前缀子串与后缀子串，来确定失配时下次对齐的位置；

其中最关键的就是next数组的确立；

数据结构课本上KMP算法next数组计算经典的例子：

void
getNext( 
const
char
*
pStr
,
int
*
nextArr) 
{ 
int
i
=
0
,
k
=
-
1
,
pLen
=
strlen( 
pStr); 
nextArr
[
i
]
=
k; 
int
mLen
=
pLen
-
1; 
while( 
i
<
mLen) 
{ 
if( 
k
==
-
1 || 
pStr
[
i
]
==
pStr
[
k
])
{ 
nextArr
[
++
i
]
=
++
k; 
}
else
k
=
nextArr
[
k
];
}
}

而这个KMP算法next数组计算只关注了前k-1个字符中，前后匹配的子串，没有利用到当前失配的字符；

比如：ABACA，当第2个A失配时，说明被匹配串的当前位置的字符必定不等于A，所以将第0位对齐到此位也必定失配，所以应该继续回溯到第0位失配时所需要对齐的位，这里也就是-1；

这个"必定不等于(!=)"是可以被利用的！我们对KMP算法next数组计算的优化正是基于此；

下面是优化后的KMP算法next数组计算与注释：

//优化过后的next数组求法
void
getNext( 
const
char
*
pStr
,
int
*
nextArr) 
{ 
int
j
=
0
,
j_next
=
-
1
,
pLen
=
strlen( 
pStr); 
nextArr
[
j
]
=
j_next; 
//此处第0位失配，则对齐第-1位；
int
mLen
=
pLen
-
1; 
while( 
j
<
mLen) 
{ 
//基于第j位与第j_next已经相等（或者j_next为-1）
//广义地将空字符（pStr[-1]）看做可以与任意字符相等，这样很益于理解
//求下一个j失配时的对齐位
if( 
pStr
[
++
j
]
!=
pStr
[
++
j_next
])
{ 
//因为（自增++之后）pStr[j]与pStr[j_next]不相等
//所以此时pStr[j]失配后，可以用pStr[j_next]来试试，所以nextArr[j] = j_next;
nextArr
[
j
]
=
j_next; 
//因为此时pStr[j]与pStr[j_next]不相等
//所以回溯取pStr[j_next]失配时的对齐位pStr[nextArr[j_next]]
//直到相等为止
while( 
j_next
!=
-
1
&&
pStr
[
j
]
!=
pStr
[
j_next
])
j_next
=
nextArr
[
j_next
];
}
//这里就是优化点
//因为（自增++之后）pStr[j]与pStr[j_next]相等
//所以pStr[j]失配后，pStr[j_next]也必定失配
//故丢弃pStr[j_next]，再取pStr[j_next]失配时的对齐位pStr[nextArr[j_next]]
//也即nextArr[j] = nextArr[j_next];
else
nextArr
[
j
]
=
nextArr
[
j_next
];
}
}

给个无注释纯净版的：

void
getNext( 
const
char
*
pStr
,
int
*
nextArr) 
{ 
int
j
=
0
,
j_next
=
-
1
,
pLen
=
strlen( 
pStr); 
nextArr
[
j
]
=
j_next; 
int
mLen
=
pLen
-
1; 
while( 
j
<
mLen) 
{ 
if( 
pStr
[
++
j
]
!=
pStr
[
++
j_next
])
{ 
nextArr
[
j
]
=
j_next; 
while( 
j_next
!=
-
1
&&
pStr
[
j
]
!=
pStr
[
j_next
])
j_next
=
nextArr
[
j_next
];
}
else
nextArr
[
j
]
=
nextArr
[
j_next
];
}
}