kmp算法

还真的有公司笔试考了这个填空,每次看到这个都记得不太准,kmp算法的难点就是求next数组,
遂回来仔细研究了下求next串的方法,kmp算法中主串不用回溯的的原因就是因为可以利用已知匹配来确认子串的滑动距离。

设s=” s1 s2 … sn ”, t=” t1 t2 … tm ”,在匹配过程中,当si≠ tj(1≤i≤n-m+1,1≤j≤m)时,存在(前面的j-1个字符已匹配):
si-j+1 … si-1 = t1 t2 … tj-1
若模式中存在可互相重叠的最长的真子串,满足:
t1 t2 … tk-1 =tj-k+1 tj-k+2 … tj-1

根据上式,求next串的过程,可以理解为模式串自身匹配自身,则有t1 t2 … tk-1 =tj-k+1 tj-k+2 … tj-1,而t(k) == t(j) , 则next[j+1] = next[j] + 1,否则就next[j+1] = next[k`] + 1 ,这个k`要一直0或者t(j) = t(next[k]) …

书上的代码都是字符串从下标1开始,next也从下标1开始。。。这些贴出从下标0开始的


void get_next(const char *s, int *next)
{
     int i=0,j=-1;
     next[0] = -1;
     while(s[i])
     {
          if( j == -1 || s[i] == s[j])
          {
              i++;
              j++;
              next[i] = j;
          }
          else
              j = next[j];
     }
 }

 int kmpfind(const char *t, const char *s,int *next)
 {
     int i = 0,j=0;
     int lena = strlen(t);
     int lenb = strlen(s);
     while(i < lena && j < lenb)
     {
                if(j == -1 || t[i] == s[j])
                {
                     i++;
                     j++;
                     if(s[j] == '\0')
                        return i - j;
                 }
                else
                    j = next[j];
     }
     return -1;
 }
转载请注明来源:Leoncom-《kmp算法》
, ,
Trackback

no comment untill now

Add your comment now