一篇文章带你了解C++的KMP算法
短信预约 -IT技能 免费直播动态提醒
KMP算法
KMP算法作用：字符串匹配
例如母串S = “aaagoogleaaa”;
子串T= “google”;
步骤1：先计算子串中的前后缀数组Next
| g | o | o | g | l | e |
|---|---|---|---|---|---|
| next[0] | next[1] | next[2] | next[3] | next[4] | next[5] |
| -1 | 0 | 0 | 0 | 1 | 0 |
C++代码：
//步骤1：
void GetNext(string Tsub, vector<int>& Next)
{
int j = 0, k = -1;
Next[0] = k;
while (j < Tsub.length() - 1)
{
if (k == -1 || Tsub[j] == Tsub[k])
{
Next[++j] = ++k;
}
else
{
k = Next[k];
}
}
}
步骤2：查找子串在母串中出现的位置。
//步骤2：
int KMP(string S, string T, vector<int> Next)
{
int i = 0, j = 0;
int m = S.length();
int n = T.length();
while (i < m && j < n)
{
if (j == -1 || S[i] == T[j])
{
i++;
j++;
}
else
{
j = Next[j];
}
}
if (j == n)
{
return i - j;
}
else
{
return -1;
}
}
结合上面两个步骤写出完整代码：
#include <iostream>
#include <vector>
using namespace std;
//步骤1：
void GetNext(string Tsub, vector<int>& Next)
{
int j = 0, k = -1;
Next[0] = k;
while (j < Tsub.length() - 1)
{
if (k == -1 || Tsub[j] == Tsub[k])
{
Next[++j] = ++k;
}
else
{
k = Next[k];
}
}
}
//步骤2：
int KMP(string S, string T, vector<int> Next)
{
int i = 0, j = 0;
int m = S.length();
int n = T.length();
while (i < m && j < n)
{
if (j == -1 || S[i] == T[j])
{
i++;
j++;
}
else
{
j = Next[j];
}
}
if (j == n)
{
return i - j;
}
else
{
return -1;
}
}
int main()
{
string S = "aaagoogleaaa";
string T = "google";
vector<int> Next(T.length());
GetNext(T, Next);
int retVal = KMP(S, T, Next);
if (retVal == -1)
{
std::cout << "can't Index" << std::endl;
}
else
{
std::cout << "Index :" << retVal << std::endl;
}
return 0;
}
总结
本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注编程网的更多内容！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
