KMP解析
本帖最后由 Sharing 于 2013-6-10 21:52 编辑原文出处http://blog.csdn.net/sharing_li/article/details/8822946
先看字符串S“abcdex”和T"abcdx"，比较的时候，两字符串都从下标0开始比较，直到S = 'e' != T = 'x'。然后S从下标1开始，T从下标0开始继续比较。我们可以发现，这是没必要的，在T中，T和T,T和T,T和T都不相等，因为T = S,T = S,T = S，所以T和S,S,S都不相等，所以就没有必要和它们比较，直接从S的下标4开始，T的下标0开始比较。我们还会发现，比较的过程中,S的下标 i 不会后退，i 要么原地踏步，要么向前进，但是T的下标 j 是可以后退、原地踏步和前进的。所以我们在比较的过程中，当有S != T 时，i 不后退，将 j 后退到合适的位置。我们用next数组保存 j 后退的适当位置。j = next 就表示但串T第 j 个字符与S对应字符不想等时，下标 j 退到适当的位置。那我们怎么确定j要后退到哪里呢？我们先来看看下面一些求next数组的例子：
1.T = "abcdex"
j : 0 1 2 3 4 5
T : a b c d e x
next : -1 0 0 0 0 0
1）j = 0时：一开始就不相等，则j无路可退，我们定义next = -1，-1表示 j = 0是j无路可退；
2）j = 1时：下标0到 j - 1所组成的字符串是“a”，j退到下标0的位置，next = 0；
3）j = 2时：下标0到 j - 1所组成的字符串是“abc”,j还是退到下标0的位置,next = 0;
4）同理
5）同理
6）同理
2.T = "abcabx"
j : 0 1 2 3 4 5
T : a b c a b x
next : -1 0 0 0 1 2
1）j = 0时，同理next = -1；
2）j = 1时，同理next = 0；
3）同理
4）同理
5）j = 4时，下标0到 j - 1所组成的字符串是“abca”，可以发现前缀T和后缀T相等，我们之后都用绿色表示前缀，红色表示后缀，此时 j 应该后退到 j = 1处，即next = 1。想一想，为什么？因为T和S比较时，S = a,S = b,而T和T相等，T又和S相等，所以S == T。则下次比较时，T从下标1开始。
6）j = 5时，下标0到 j - 1所组成的字符串是“abcab”，可以发现前缀T = "ab" = 后缀 T，所以 j 后退到 j= 2处，即next = 2；
可以发现，j 后退的位置为前缀和后缀的相似度，再看两个例子：
3. T = “ababaaaba”
j : 0 1 2 3 4 5 6 7 8
T : a b a b a a a b a
next : -1 0 0 1 2 3 1 1 2
1）j = 0时，next = -1；
2）j = 1时，next = 0；
3）同理；
4）j = 3时，下标0到 j - 1所组成的字符串是“aba”,前缀为a,后缀为a,相似度为1，所以next = 1；
5）j = 4时，下标0到 j - 1所组成的字符串是“abab”，前缀为ab，后缀为ab，相似度为2，next = 2；6）j = 5时，下标0到 j - 1所组成的字符串是“ababa”，前缀为aba，后缀为aba，相似度为3，next = 3；
7）j = 6时，下标0到 j - 1所组成的字符串是“ababaa”，前缀为a，后缀为a，相似度为1，next = 1；
之后同理。
算法实现如下：
#include<stdio.h>
#include<string.h>
void GetNext(char * T,int * next)
{
int i = 0,j = -1;
next = -1;
while(i < strlen(T))
{
if (j == -1 || T == T)//T表示后缀的单个字符,T表示前缀的单个字符
{
i++;
j++;
next = j;
}
else
{
j = next;//若字符串不同，则j值后退
}
}
}
int KMP(char * S,char * T)
{
int i = 0;//i为主串S当前位置下标
int j = 0;//j为字串T当前位置下标
int next;//为什么是255?想想char的范围
int S_len = strlen(S),T_len = strlen(T);
GetNext(T,next);//得到T的next数组
while (i < S_len && j < T_len)
{
if (j == -1 || S == T)//两字符相等则继续比较
{
i++;
j++;
}
else//若不相等,则i不后退,j后退到合适的位置
{
j = next;
}
}
if (j == strlen(T))//若存在
return 1;
else
return 0;
}
int main()
{
char * s = "abcdaefg", * t = "bcd";
if (!KMP(s,t))
{
printf("不存在！\n");
}
else
{
printf("存在！\n");
}
return 0;
}
接下来，想想KMP算法是否可以改进？看看一个例子：S = "aaaabcde" ，T = “aaaaax”，T的next数组值为｛-1，0，1，2，3，4｝，但S != T时，j = next =3，此时S != T，j = next = 2，此时S != T，知道j = 0。我们可以发现，其实我们可以直接把 j 退到 0，减少一些不必要的计算，修改GetNext函数如下：
void GetNext(char * T,int * next)
{
int i,j;
i = 0;
j = -1;
next = -1;
while(i < strlen(T))
{
if (j == -1 || T == T)//T表示后缀的单个字符,T表示前缀的单个字符
{
i++;
j++;
if (T != T)//若当前字符与前面一个字符不相等
next = j;
else
next = next;
next = j;
}
else
{
j = next;//若字符串不同，则j值后退
}
}
}原文出处http://blog.csdn.net/sharing_li/article/details/8822946
无回帖，不论坛，这才是人道。 楼主ing…… 值得学习··· 修改Next后的 next = j;不就重复了吗？ 4始终实行， 那 1 跟 3那不就米意义了？
0if (T != T)//若当前字符与前面一个字符不相等
1next = j;
2else
3next = next;
4next = j; {:5_95:}````````````````````````` Cong3 发表于 2013-8-24 10:34 static/image/common/back.gif
修改Next后的 next = j;不就重复了吗？ 4始终实行， 那 1 跟 3那不就米意义了？
0if (T != T) ...
我也不明白这里，不要第四步，得出的next值又好像是错的，不明白了 楼主ing…… 好文章转过来方便自己看，，，，，， 马克 ！回头学了ＫＭＰ 回来看看 求解释，我也遇到同样的问题了 我是来打酱油的..!~ 我是来打酱油的..!~
看毛片算法:lol: 谢谢楼主分享！努力学习中。这个算法理解以及手工解题（next[]、nextval[]）太简单了，只是难于用代码表示。
页:
[1]