KMP算法中求next数组的实质

时间:2022-04-13 23:04:37

在串匹配模式中,KMP算法较蛮力法是高效的算法,我觉得其中最重要的一点就是求next数组:

看了很多资料才弄明白求next数组是怎么求的,我发现我的忘性真的比记性大很多,每次看到KMP算法求next数组都得花很长时间去看怎么求,虽然看了很多遍了,但还是容易忘,所以我今天非得把它记下来,这样我下次看到的时候就可以直接看我的总结了,哈,可恶的记性,总是这么不争气。设目标串为S,需要匹配串为T:

next[j]数组生成的实质:

    next[j]数组的值其实就等于串T1T2...Tj-1中相同的前缀子串和后缀子串的最大长度加1。再则找前缀和后缀相同的最大真子串,实质上仍然是一个模式匹配,只是匹配的模式串和目标串是同一个串T。所以就有:

1、next[1]=0

2、设next[j]=k

     若Tk=Tj时,则 next[j+1]=next[j]+1

     若Tk≠Tj , 则 next[j+1]=next[k]+1

3. 若不存在匹配的子串:  next[j+1]=1

例:已知匹配串t=“abcaabbabcab”,则:

模式t:   a  b  c  a  a  b  b  a  b   c  a   b

next[j]: 0  1  1  1  2  2  3  1  2   3  4   5

next函数的算法:

void next(string t,int next[])

{

   int j=1,k=0;

   next[1]=0;

   while(j<t.len)

  {

      if(k=0||t.str[j]==t.str[k])

      {

           j++;k++;next[j]=k;

      }

      else

            k=next[k];  

  }

}