KMP解析

Sharing

原文出处http://blog.csdn.net/sharing_li/article/details/8822946
先看字符串S“abcdex”和T"abcdx"，比较的时候，两字符串都从下标0开始比较，直到S[4] = 'e' != T[4] = 'x'。然后S从下标1开始，T从下标0开始继续比较。我们可以发现，这是没必要的，在T中，T[0]和T[1],T[0]和T[2],T[0]和T[3]都不相等，因为T[1] = S[1],T[2] = S[2],T[3] = S[3]，所以T[0]和S[1],S[2],S[3]都不相等，所以就没有必要和它们比较，直接从S的下标4开始，T的下标0开始比较。我们还会发现，比较的过程中,S的下标 i 不会后退，i 要么原地踏步，要么向前进，但是T的下标 j 是可以后退、原地踏步和前进的。所以我们在比较的过程中，当有S != T[j] 时，i 不后退，将 j 后退到合适的位置。我们用next数组保存 j 后退的适当位置。j = next[j] 就表示但串T第 j 个字符与S对应字符不想等时，下标 j 退到适当的位置。那我们怎么确定j要后退到哪里呢？我们先来看看下面一些求next数组的例子：
1.T = "abcdex"
j          :   0    1     2     3    4    5

T         :   a    b     c     d    e     x
next[j] : -1    0     0     0    0     0


1）j = 0时：一开始就不相等，则j无路可退，我们定义next[0] = -1，-1表示 j = 0是j无路可退；
2）j = 1时：下标0到 j - 1所组成的字符串是“a”，j退到下标0的位置，next[1] = 0；
3）j = 2时：下标0到 j - 1所组成的字符串是“abc”,j还是退到下标0的位置,next[2] = 0;
4）同理
5）同理

6）同理
2.T = "abcabx"

j          :   0    1     2     3    4    5

T         :   a    b     c     a    b     x

next[j] : -1    0     0     0    1     2

1）j = 0时，同理next[0] = -1；
2）j = 1时，同理next[1] = 0；
3）同理
4）同理
5）j = 4时，下标0到 j - 1所组成的字符串是“abca”，可以发现前缀T[0]和后缀T[3]相等，我们之后都用绿色表示前缀，红色表示后缀，此时 j 应该后退到 j = 1处，即next[4] = 1。想一想，为什么？因为T和S比较时，S[3] = a,S[4] = b,而T[0]和T[3]相等，T[3]又和S[3]相等，所以S[3] == T[0]。则下次比较时，T从下标1开始。
6）j = 5时，下标0到 j - 1所组成的字符串是“abcab”，可以发现前缀T[0~1] = "ab" = 后缀 T[3~4]，所以 j 后退到 j  = 2处，即next[5] = 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[j] : -1    0      0    1    2     3     1     1    2

1）j = 0时，next[0] = -1；
2）j = 1时，next[1] = 0；
3）同理；
4）j = 3时，下标0到 j - 1所组成的字符串是“aba”,前缀为a,后缀为a,相似度为1，所以next[3] = 1；

5）j = 4时，下标0到 j - 1所组成的字符串是“abab”，前缀为ab，后缀为ab，相似度为2，next[4] = 2；6）j = 5时，下标0到 j - 1所组成的字符串是“ababa”，前缀为aba，后缀为aba，相似度为3，next[5] = 3；
7）j = 6时，下标0到 j - 1所组成的字符串是“ababaa”，前缀为a，后缀为a，相似度为1，next[6] = 1；
之后同理。

算法实现如下：

#include<stdio.h>
#include<string.h>
void GetNext(char * T,int * next)
{
 int i = 0,j = -1;
 next[0] = -1;
 while(i < strlen(T))
 {
  if (j == -1 || T[i] == T[j])//T[i]表示后缀的单个字符,T[j]表示前缀的单个字符
  {
   i++;
   j++;
   next[i] = j;
  }
  else
  {
   j = next[j];//若字符串不同，则j值后退
  }
 }
}
int KMP(char * S,char * T)
{
 int i = 0;//i为主串S当前位置下标
 int j = 0;//j为字串T当前位置下标
 int next[255];//为什么是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[i] == T[j])//两字符相等则继续比较
  {
   i++;
   j++;
  }
  else//若不相等,则i不后退,j后退到合适的位置
  {
   j = next[j];
  }
 }
 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[4] != T[4]时，j = next[4] =3，此时S[4] != T[3]，j = next[3] = 2，此时S[4] != T[2]，知道j = 0。我们可以发现，其实我们可以直接把 j 退到 0，减少一些不必要的计算，修改GetNext函数如下：

void GetNext(char * T,int * next)
{
 int i,j;
 i = 0;
 j = -1;
 next[0] = -1;
 while(i < strlen(T))
 {
  if (j == -1 || T[i] == T[j])//T[i]表示后缀的单个字符,T[j]表示前缀的单个字符
  {
   i++;
   j++;
   if (T[i] != T[j])//若当前字符与前面一个字符不相等
    next[i] = j;
   else
    next[i] = next[j];
   next[i] = j;
  }
  else
  {
   j = next[j];//若字符串不同，则j值后退
  }
 }
}

原文出处http://blog.csdn.net/sharing_li/article/details/8822946

lsh華

无回帖，不论坛，这才是人道。

古来圣贤皆寂寞

楼主ing……

一敏阳光

值得学习···

Cong3

修改Next后的 next[i] = j;不就重复了吗？    4始终实行， 那 1 跟 3那不就米意义了？

0  if (T[i] != T[j])//若当前字符与前面一个字符不相等
1  next[i] = j;
2  else
3  next[i] = next[j];
4  next[i] = j;

蒍嗳變乖/ka

`````````````````````````

付笑

Cong3 发表于 2013-8-24 10:34

                               
登录/注册后可看大图

修改Next后的 next = j;不就重复了吗？    4始终实行， 那 1 跟 3那不就米意义了？

0  if (T != T[j]) ...

我也不明白这里，不要第四步，得出的next值又好像是错的，不明白了

sako_sc

楼主ing……

猪猪BBUn咕咕

好文章转过来方便自己看，，，，，，

T_未命名

马克 ！回头学了ＫＭＰ　回来看看

星空夜谈

求解释，我也遇到同样的问题了

ヽ朝暮是安然

我是来打酱油的..!~

tt1122

我是来打酱油的..!~

loveyaqin1990

看毛片算法:lol:

Kitty喜欢小鱼干

谢谢楼主分享！努力学习中。这个算法理解以及手工解题（next[]、nextval[]）太简单了，只是难于用代码表示。