欢迎前往个人博客 驽马点滴 和视频空间 哔哩哔哩-《挨踢日志》
先引两篇看过的文章：
http://blog.csdn.net/v_july_v/article/details/6545192
http://blog.csdn.net/v_july_v/article/details/7041827
里面介绍得不错。
KMP算法的关键在于next[j]函数，明白了这个，才会真正掌握KMP算法。
这里只想写写自己对next[j]函数的分析。
【问题背景】S中寻找子串P
【关键】求出P的next[j]函数
k=next[j]函数表示的意思首先要明白: 在S[i]与P[j]不匹配的时候，S[i]继续和P中的项P[k]进行匹配（当然k!=-1）;
k=next[j]函数蕴含的意思也要明白:P[0:k-1]和P[j-k:j-1]是相互匹配的最长子串;
弄明白以上两点，一切问题迎刃而解：
我们的目的不就是已知0:j时的next[j]求next[j+1]吗？
那么先令k=next[j];且假设S[i+1]不匹配P[j+1]，下面求next[j+1]。
考虑
P[j]==P[k], 那么在加上已知的【关键】2 我们知道 P[0:k]和P[j-k:j]匹配，但此时，我们还关心P[j+1]和P[k+1]是否相等：如果P[j+1]!=P[k+1]，意味着P[0:k]和P[j-k:j]这是最长的匹配子段，那么S[i+1]下一个需要进行匹配的项是P[k+1]，即知道next[j+1]=k+1;
如果P[j+1]==P[k+1]，而已知S[i+1]!=P[j+1]，那么有S[i+1]!=P[k+1]，于是S[i+1]就不需要和P[k+1]进行比较（但是我们知道S[i-k:i]和P[0:k]是相互匹配的（S[i-j:i]和P[0:j]匹配，再加上下滑线的部分： P[0:k]和P[j-k:j]匹配 可得）），于是由于S[i+1]不匹配P[k+1]而需要“更改下一个匹配项”，而这个匹配项，按照定义即next[k+1]，因此next[j+1]=next[k+1];
P[j]!=P[k],那么首先由【关键】2得 P[0:k-1]和P[j-k:j-1]是相互匹配的，但是下一项P[k]和P[j]不匹配，看到了吗？如果把P[0:k]看成子串P',把P[0:j]看成S'，那么此时j项不匹配k项的时候，j项下一个去匹配的应该是哪项？对了，是next[k]（因此要让k=next[k]，回到1.，目的是使得P[j]==P[k]，这样，才能求出next[j+1]）;
这就是整个next[j+1]函数的由来.
代码看看今晚能不能自己写出来。
HX 2013-1-16.
#include "stdafx.h"
#include<iostream>
#include<string>
using namespace std;
void GetNext(char const* p, int plength, int* next)
{
int j = 0;
int k = -1;
next[j]=-1;
while(j<plength-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 KMPAlgorithm(char const* s, int slength, char const* p, int plength,int* next)
{
int i=0;
int j=0;
while(i<slength&&j<plength)
{
if(j==-1||s[i]==p[j])
{
++i;
++j;
}
else
{
j=next[j];
}
}
if(j>=plength)
{
return i-plength;
}
else
{
return -1;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
string sstring = "aabbacbcabababbababccc";
string pstring = "ababc";
int* next = new int [pstring.size()];
GetNext(pstring.data(),pstring.size(),next);
for(int i=0;i<pstring.size();i++)
{
cout<<next[i]<<"\t";
}
cout<<endl;
int kmpResult = KMPAlgorithm(sstring.data(),sstring.size(),pstring.data(),pstring.size(),next);
cout<<"返回值"<<kmpResult<<endl;
cout<<"子串为："<<sstring.substr(kmpResult,pstring.size())<<endl;
system("pause");
delete[] next;
return 0;
}
【结果】
