KMP

最新推荐文章于 2025-06-02 20:51:47 发布

yottapeng

最新推荐文章于 2025-06-02 20:51:47 发布

阅读量478

点赞数

分类专栏：算法文章标签：算法 kmp

算法专栏收录该内容

6 篇文章

订阅专栏

KMP的优势就在于可以让模式串向右滑动尽可能多的距离
就是abc直接从模式串的第三个字母aba...开始匹配，为了实现这一目标，KMP需要预处理出模式串的next数组
理解KMP的关键是你要理解next数组，next数组中保存的就是一个模式串的后缀与前缀的最长匹配，即next[i]=max(len),使得next[0]=next[i-len],next[1]=next[i-len+1]...,next[len-1]=next[i-1], 比如aaabcaaa这么一个串，那么它的next数组的值应该依次为
next[0]=-1,next[1]=0,next[2]=1,next[3]=2,next[4]=0,next[5]=0,next[6]=1,next[7]=2,next[8]=3.

void get_next(char *T,int *next,int len)
{
  int j=0,k=-1;
  next[0]=-1;
  while(j<=len)
  {
    if(k==-1||T[j]==T[k])
    {
      j++;k++;
      next[j]=k;
    }
    else
      k=next[k];
  }
}

插段获取next数组的代码题主自己体会一下，其实就是模式串自己和自己匹配一次，然后是两个字符串匹配的代码

int KMP(char *A,char *B,int len,int len2)
{
    int *next=new int[len+5];
    get_next(B,next,len);
    int i=0,j=0,ans=0;
    while(i<len2)
    {
        if(j==-1||A[i]==B[j])
            i++,j++;
        else
            j=next[j];
        if(j==len)
        {
            ans++;
            j=0;
        }
    }
    return ans;
}