KMP算法
标签：names ++ main mp算法 算法 string class out span
重点：理解next数组的含义，减少循环的时间。
#include using namespace std;
const int N=10005;
int next[1005];
//优化过后的next 数组求法
void GetNextval(string p)
{
int pLen = p.length();
next[0] = -1;
int k = -1;
int j = 0;
while (j 1)
{
if (k == -1 || p[j] == p[k])
{
++j;
++k;
if (p[j] != p[k])
next[j] = k; //之前只有这一行
else
next[j] = next[k];
}
else
{
k = next[k];
}
}
}
int kmp(string s,string p)
{
int i = 0;
int j = 0;
int sLen = s.length();
int pLen = p.length();
while (i pLen)
{
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
j = next[j];
}
}
if (j == pLen)
return i - j;
else
return -1;
}
int main()
{
string s1,s2;
cin>>s1>>s2;
GetNextval(s2);
coutendl;
}
KMP算法
标签：names ++ main mp算法 算法 string class out span
原文地址：https://www.cnblogs.com/lhlccc/p/11621962.html
文章来自：
搜素材网的
编程语言模块，转载请注明文章出处。
文章标题：
KMP算法
文章链接：http://soscw.com/essay/36554.html
评论