【原创】史上最透彻的KMP算法讲解

1

字符串匹配是经典的KMP算法。下面以字符串"BBC ABCDAB ABCDABCDABDE"为例，查找是否包含串"ABCDABD"？

图一

2

首先如上图，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜词"ABCDABD"的第一个字符，B与A不相等，所以后移动。

图二

3

上图中，D与空格不相等，但是它有前缀AB与后缀AB相当，KMP的思想就是利用最长的公共前缀与最长公共后缀相等，来加快每次不相等时移动的距离，来提高搜索效率。

4

要做到这一点，就是要生成一个next匹配数组，next匹配数据来决定匹配的最大长度。如图二。查next数组可知，最后一个匹配字符B对应的"部分匹配值"为2，因此后移动的位数：移动位数 = 已匹配的字符数 - 对应的部分匹配值。因为 6 - 2 等于4，所以将搜索词向后移动4位。

下面是next数组和匹配算法参照代码。

精彩内容

#include <iostream>

#include <cstring>

using namespace std;

const int N = 1000002;

int next[N];

char S[N], T[N];

int slen, tlen;

void getNext()

{

int j, k;

j = 0; k = -1; next[0] = -1;

while(j < tlen)

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

next[++j] = ++k;

else

k = next[k];

}

/*

返回模式串T在主串S中首次出现的位置

返回的位置是从0开始的。

*/

int KMP_Index()

{

int i = 0, j = 0;

getNext();

while(i < slen && j < tlen)

{

if(j == -1 || S[i] == T[j])

{

i++; j++;

}

else

j = next[j];

}

if(j == tlen)

return i - tlen;

else

return -1;

}

---

---

往

期

推

荐

1.机器学习中的数据不平衡解决方案大全

2.【万字长文】AI大行其道，你准备好了吗

3.2019最新BAT、TMD等等公司技术面试题及其答案