不知道看了几遍的kmp，反正到现在都没有弄清楚next[j]的计算和kmp的代码实现，温故而知新，经常回来看看，相信慢慢的就回了
从头到尾彻底理解KMP
理解KMP
/*!
* \file KMP_算法.cpp
*
* \author ranjiewen
* \date 2017/02/12 16:12
*
*/ void preKmp(const char* pattern, int m, int kmpNext[]) //和GetNextval等价
{
int i, j;
i = ;
j = kmpNext[] = -;
while (i<m)
{
while (j>- && pattern[i] != pattern[j]) // i为后缀，j为前缀
{
j = kmpNext[j];
}
i++;
j++;
if (pattern[i] == pattern[j])
{
kmpNext[i] = kmpNext[j];
}
else
{
kmpNext[i] = j;
}
}
} #include <iostream>
using namespace std;
#include <string> void KMP(string p, string t)
{
int m = p.length();
int n = t.length();
if (m>n)
{
cerr << "Unsuccessful match!";
}
const char* x = p.c_str();
const char* y = t.c_str(); int i = , j = , kmpNext[];
preKmp(x, m, kmpNext); i = j = ;
while (i<n)
{
while (j>- && x[j] != y[i])
{
j = kmpNext[j];
}
j++;
i++;
if (j >= m)
{
cout << "Matching index found at:" << i - j << endl;
j = kmpNext[j];
}
}
}
int main(int argc, char** argv) { string p1 = "abcabcad";
string p2 = "adcadcad";
string p3 = "ababcaabc";
string t = "ctcabcabcadtcaabcabcadat"; cout << "KMP: " << endl;
KMP(p1, t); // cout<<"KMP: "<<endl;
// KMP(p2, t); // cout<<"KMP: ";
// KMP(p3, t); return ;
}
以后kmp算法都按照这样写
void GetNext(char* p, int next[])
{
int pLen = strlen(p);
next[] = -;
int k = -;
int j = ;
while (j < pLen - ) //j<pLen也没有错
{
//p[k]表示前缀，p[j]表示后缀
if (k == - || p[j] == p[k])
{
++k;
++j;
next[j] = k; //对于值k，已有p0 p1, ..., pk-1 = pj-k pj-k+1, ..., pj-1，相当于next[j] = k。
}
else //当不匹配时，更新新的前缀下标
{
k = next[k];
}
}
} // 优化的地方
//当p[j] != s[i] 时，下次匹配必然是p[next[j]] 跟s[i]匹配，如果p[j] = p[next[j]]，必然导致后一步匹配失败（因为p[j]已经跟s[i]失配，
//然后你还用跟p[j]等同的值p[next[j]]去跟s[i]匹配，很显然，必然失配），所以不能允许p[j] = p[next[j]]。
//优化过后的next 数组求法
void GetNextval(char* p, int next[])
{
int pLen = strlen(p);
next[] = -;
int k = -; //前缀
int j = ;
while (j < pLen - ) //j<pLen也没有错
{
//p[k]表示前缀，p[j]表示后缀
if (k == - || p[j] == p[k])
{
++j;
++k;
//较之前next数组求法，改动在下面4行
if (p[j] != p[k])
next[j] = k; //之前只有这一行
else
//因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
next[j] = next[k];
}
else
{
k = next[k];
}
}
} int KmpSearch(char* s, char* p)
{
int i = ;
int j = ;
int sLen = strlen(s);
int pLen = strlen(p); int next[] = { };
GetNextval(p,next); while (i < sLen && j < pLen)
{
//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
if (j == - || s[i] == p[j])
{
i++;
j++;
}
else
{
//②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
//next[j]即为j所对应的next值
j = next[j];
}
}
if (j == pLen)
return i - j; //此处i-j才是字符串开始匹配的地方
else
return -;
}
有这样写的，else效果就是j==-1的时候
while (Text[i] != '\0' && Pattern[j] != '\0')
{
if (Text[i] == Pattern[j])
{
++i;// 继续比较后继字符
++j;
}
else
{
index += j - next[j];
if (next[j] != -)
j = next[j];// 模式串向右移动
else
{
j = ;
++i;
}
}
}//while
