大话KMP算法（原创）
最近在学习数据结构。遇到KMP算法的时候，研究了好几天，终于弄明白了算法的思想。
今天心情很不爽（因为被二叉树给难住了，哎！）。就写一下KMP算法吧。望编程高手给予指点。
请注意，在看这篇文章之前，请务必先看看严蔚敏老师的《数据结构》中的串的模式匹配算法（P79）这一节，在看不
懂KMP算法的时候再看下面这篇文章。当然，基本的模式匹配算法请务必先看懂。
KMP算法思想：1.设S为主串（目标串），T为模式串，以i和j分别指示主串和模式串中正待比较的字符，若Si=Tj，则i
和j分别加1，继续比较Si和Tj（其实，这个时候是比较Si+1和Tj+1了）；否则，i不变，而j退回到j=next[j]的位置，
继续比较Si和Tj（其实，这个时候是比较Si和Tnext[j]）。以上两种情况是，若新的Si=Tj，则i和j分别加1，继续往后
比较，若不相等，则j接着退到下一个j=next[j]的位置，再比较新的Si和Tj。直到下列两种情况之一：一是j退回到某
个j=next[j]的位置时，有Si=Tj，则i和j各加1继续往后比较；二是j退回到j=0时（即模式串的第1个字符失配），则将
从Si+1和T1重新开始往后比较。
1.KMP算法//利用模式串中的next函数求Tj!=Si是，指针j应退回的位置
int Index_KMP(SString S,SString T,int pos)
{
int i,j;
i=pos;
j=1;
while(i<=S[0] && j<=T[0])
{
if(j==0 || j<=T[j])//j==0表示模式串中第一个字符即和Si失配，则应从Si+1和T1开始重新比较
{
++i;
++j;
}
else
{
j=next[j];//即next[j]=k,j应退回到k的位置，即从Si和Tk开始重新比较
}
}
if(j>T[0])
return i-T[0];
else
return 0;
}
2.接下来就是如何求next[j]了。因为已知next[1]=0，之一找出next[j+1]与next[j]之间的关系，就可以求出模式串中
所有的next[j]。
初始算法：
(1)初值next[1]=0；
(2)设next[j]=k，于是有"T1......Tk-1"="Tj-k+1......Tj-1";
(2-1)若Tj=Tk，则有"T1......Tk-1Tk"="Tj-k+1......Tj-1Tj";故此时有next[j+1]=k+1=next[j]+1。
(2-2)若Tj!=Tk,设next[k]=k',则有"T1......Tk'-1"="Tj-k'+1......Tj-1"。
(2-1-1)若Tj=Tk',则next[j+1]=k'+1=next[k]+1=next[next[j]]+1;
(2-1-2)若Tj!=Tk',则重复(2-2)直到不存在kn为止，则此时有next[j+1]=1。
2.求next函数的算法(求模式串T的next函数值并存入数组next中)
void get_next(SString T,int next[])//因为形参是数组，故不需要引用类型
{
int j,k;
j=1;
next[j]=k=0;//写成这样是因为我觉得更好理解一点
while(j<T[0])
{
if(k==0 || T[j]==T[k])没有重叠真子串或有重叠真子串但T[j]==T[k]时,都可求出next[j+1]的值
{
++j;
++k;
next[j]=k;//其实，这三句等价于next[++j]=++k;即next[j+1]=next[j]+1
}
else //否则(即有重叠真子串，但此时T[j]!=T[k])，则此时无法求出next[j+1]的值，那么此时
k=next[k];子串T应再跳到k'= next[k]去匹配，直到kn=0或者T[j]=T[kn]
}
}
//k==0表示没有重叠真子串（next[j]=k=0），此时应该从Si+1与T1开始比较。那么当Tj+1与Si'不匹配时,next[j+1]
=1.即i'不变，子串从T1开始一Si'开始向后比较。
//T[j]==T[k]表示有重叠真子串，但此时亦有T[j]=T[k].则此时有next[j+1]=next[j]+1
3.但是，上面的思想还有一个缺陷，在求出next[j]=k时，若T[j]=T[k]，则由于T[j]!=S,必然有T[k]也不会等于S
，此时就要继续k'=next[k],直到T[j]!=T[kn].此即nextval[]数组的求法。
3.求nextval函数的算法
void get_nextval(SString T,int nextval[])
{
j=1;
nextval[j]=k=0;
while(j<T[0])
{
if(k==0 || T[j]==T[k])
{
++j;
++k;
if(T[j]!=T[k])
nextval[j]=k;//这时T[j]实际上是T[j+1],T[k]实际上是T[k+1]
else
nextval[j]=nextval[k];
}
else
k=next[k];//否则，j不变，k退回到next[k]的位置
}
}
在实际运用时，只需要1和3即可。即只需要Index_kmp和get_nextval两个即可。
注：不是我不注重编程规范，而是文本格式的限制，我也没办法。先凑合着吧，反正算法注重的是思想。一点格式问题也不要紧了哈...
转载请注明出自暗组信息安全论坛 http://forum.darkst.com/,本贴地址:http://forum.darkst.com/viewthread.php?tid=56082