KMP 算法是一种改进的字符串匹配算法,KMP 算法是由 D.E.Knuth,J.H.Morris 和 V.R.Pratt 三人提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称 KMP 算法)。KMP 算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个 next() 函数实现,函数本身包含了模式串的局部匹配信息。
有一个文本串 S 和一个模式串 P,现在要查找 P 在 S 中的位置。如果用暴力匹配的思路,
并假设现在文本串 S 匹配到 i 位置,模式串 P 匹配到 j 位置,则有:
int violenceSearch(const std::string& str, const std::string& match)
{
int strLen = str.size();
int matchLen = match.size();
if (strLen < matchLen)
return -1;
int i = 0;
int j = 0;
while (i < strLen && j < matchLen)
{
if (str[i] == match[j])
{
i++;
j++;
}
else
{
i = i - j + 1;
j = 0;
}
}
return j == matchLen ? i - j : -1;
}
模式串ABCABD
计算出部分匹配表,匹配表如下:
字符 | A | B | C | A | B | D |
---|---|---|---|---|---|---|
匹配值 | 0 | 0 | 0 | 1 | 2 | 0 |
/**
* 部分匹配值就是前缀和后缀的最长共有元素的长度。假设一个字符串 "hello",它的前缀有 h、he、hel、hell,
* 它的后缀有 ello、llo、lo、o。
*
* 假设模式字符串为:ABCAB
*
* A 没有前缀和后缀,公有元素长度为 0
* AB 的前缀有 A,后缀有 B,公有元素长度为 0
* ABC 的前缀有 A、AB,后缀有 BC、C,公有元素长度为 0
* ABCA 的前缀有 A、AB、ABC,后缀有 BCA、CA、A,公有元素长度为 1
* ABCAB 的前缀有 A、AB、ABC、ABCA,后缀有 BCAB、CAB、AB、B,公有元素长度为 2
* ABCABD 的前缀有 A、AB、ABC、ABCA、ABCAB,后缀有 BCABD、CABD、ABD、BD、D,公有元素长度为 0
* 所以 ABCABD 中每个字符对于的匹配值分别为 0、0、0、1、2、0。
*/
std::vector<int> getNext(const std::string &match)
{
int k = 0;
int len = match.size();
std::vector<int> next(len, 0);
for (int i = 1; i < len; ++i)
{
if (k > 0 && match[k] != match[i])
k = next[k - 1];
if (match[k] == match[i])
k++;
next[i] = k;
}
return next;
}
int kmp(const std::string &str, const std::string &match)
{
std::vector<int> next = getNext(match);
int k = 0;
for (int i = 0; i < str.size(); ++i)
{
if (k > 0 && match[k] != str[i])
k = next[k];
if (match[k] == str[i])
k++;
if (k == match.size())
return i - k + 1;
}
return -1;
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。