KMP算法(完整版)

刚过完国庆节,回学校,心想该静下心来好好学习了额,昨天上数据结构,听到老师已经讲到第四章了,鉴于上课从来没听过。。。顿时有点慌了,于是放下了手机,开始认真学习,那节课老师刚好讲到KMP算法,我补了补之前的课,又开始学KMP。

为啥要用KMP算法呢,为了减少不必要的回溯,当要找一个字符串 s 中是否包含一个字串 a ,以往我们的做法往往是暴力匹配,也就是BF。。。emmmm,这样的话时间复杂度为O(m*n),要是当m和n都很大的话会很不理想,于是可以用KMP算法,这个算法时间复杂度为O(m+n),很低哦。

前面说到KMP要减少不必要的回溯,那么怎样去减少不必要的回溯呢,就要用到next数组。

举个栗子:

S:“abxabcabcaby”

A:“abcaby”

要知道A是否为S的字串,按照传统做法,最开始去匹配,前两个ab都相等,当匹配到第三个时,S中为“x”,A中为“c”,不一样,于是将A再从头开始去和S匹配,再遇到不一样的,A再从头开始,这样的话每次回溯都会回溯到A中的第一个元素,只要遇到不一样的就会回溯到A中的第一个元素。

而KMP算法,是减少不必要的回溯,仔细看看,当S和A第一次匹配,发现第三个元素不一样A回溯到第一个,再与S匹配,此时S在第四个元素,A在第一个元素,a与a相同,下一个,b与b相同,下一个,c与c相同,下一个a与a相同,下一个b与b相同,再下一个S中元素为c,而A中元素为y,不相同了,这时我没无需将A回溯到第一个元素进行匹配,而是根据next数组,只需回溯两步即回溯到A中的c元素,再进行匹配,此时S中指针在c上,A中指针也在c上,继续进行匹配,后面两个元素都是b和y,相同,匹配成功。

为啥第二次匹配不成功时只回溯两步呢?
接下来说说next数组

还是先说下啥是前后缀吧。

假设一个字符串:A B A B A B A A

对应的位置就是:0 1  2  3 4  5  6 7

第0位:A的前面且不包括其本身没有元素了

第1位:B的前面有元素A,单一元素没有前后缀,

第2位:A的前面有元素AB,就AB来说前缀为A,后缀为B

第3位:B的前面有元素ABA,则字符串ABA的前缀有A,AB,后缀有A,BA

第4位:A的前面有元素ABAB,则字符串ABAB的前缀有A,AB,ABA,后缀有B,AB,BAB

第5位:B的前面有元素ABABA,则字符串ABABA的前缀有A,AB,ABAB,后缀有A,BA,ABA,BABA

···········

看到这想必就能看出来了一个字符串的前缀是(其去掉最后一个元素)的子串及其本身,后缀同理。

其实next数组记录的就是一个字符串中该位置的元素之前的字符串中前缀与后缀相同的最长长度

还是上面那个栗子:

假设一个字符串:A B A B A B A A

对应的位置就是:0 1  2  3 4  5  6 7

第0位:A的前面且不包括其本身没有元素了 next[0]=-1

第1位:B的前面有元素A,单一元素没有前后缀,于是next[1]=0

第2位:A的前面有元素AB,就AB来说前缀为A,后缀为B,无相同的,于是next[2]=0

第3位:B的前面有元素ABA,则字符串ABA的前缀有A,AB,后缀有A,BA 发现存在相同的串,长度为1,于是next[3]=1

第4位:A的前面有元素ABAB,则字符串ABAB的前缀有A,AB,ABA,后缀有B,AB,BAB 发现存在相同的串,长度为2,于是next[4]=2

第5位:B的前面有元素ABABA,则字符串ABABA的前缀有A,AB,ABA,ABAB,后缀有A,BA,ABA,BABA 发现存在相同的串,长度为3,于是next[5]=3

第6位:A的前面有元素ABABAB,则字符串ABABAB的前缀有A,AB,ABA,ABAB,ABABA,后缀有B,AB,BAB,ABAB,BABAB 发现存在相同的串,长度为4,于是next[6]=4

第7位:A的前面有元素ABABABA,则字符串ABABABA的前缀有A,AB,ABA,ABAB,ABABA,ABABABA后缀有A,BA,ABA,BABA,ABABA,BABABA 发现存在相同的串,长度为5,于是next[7]=5

看到这就知道next数组咋求了吧

求next数组代码:

第一种:

for(int i=1,k=0;i<len;i++)
    {
        while(k>0 && s[i]!=s[k])
        {k=next[k];}
        if(s[i]==s[k])
        {k++;}
        next[i+1]=k;
    }

第二种:

while(j<len)
    {
        if(k==-1 || s[j]==s[k])
        { next[++j]=++k;
        else
        {k=next[k];}
    }

关于求next数组,当时学的时候一直有个疑问,就是在代码k=next[k]这个式子是什么意思

就是当s[k]与s[j]不相同时,k会回退,可为什么会回退到next[k]呢,为啥不是k--呢?

这样想,当s[j]=s[k]时,next[++j]=++k,这代表啥,代表现在模式串(就是子串)中下标为j的元素的前k个元素与下标为k的元素的前k个元素相同

假设现在有这么个串:

A B A B A········································ A B A B C                                                                                             k                                                j

C的下标为j,A的下标为k,很明显现在next[j]=4,接下来我们要求next[j+1],于是就看s[j]和s[k],但发现s[j]=C,而s[k]=A,不相等,根据上面的代码我们进行的操作为k=next[k],为啥不是k--呢?

现在next[j]=k,代表j前面的k个元素与k前面的k个元素相同,ABAB=ABAB,是不是?现在s[j]与s[k]不同了,我们不能让next[j+1]=k+1了,怎么办呢,退一步,现在k前面的next[k]个元素与next[k]前面的next[k]个元素相同对不对,可以先算一算。

那就看s[j]与next[k]相不相同,如果相同,则继续,不相同,继续让k回到next[k],到这需要你品,细细的品。

模板例题连接:https://www.luogu.org/problem/P3375

代码:

#include <bits/stdc++.h>
using namespace std;
int next[1000010];
int main()
{
    char a[1000010];
    char b[1000010];
    scanf("%s",a);
    scanf("%s",b);
    int lb=strlen(b);
    int la=strlen(a);
    next[0]=0;
    for(int i=1,k=0;i<lb;i++)
    {
        while(k>0 && b[k]!=b[i])
            k=next[k-1];
        if(b[k]==b[i])
            k++;
        next[i]=k;
    }
    int j=0;
    for(int i=0;i<la;i++)
    {
        while(j>0 && a[i]!=b[j])
            j=next[j-1];
        if(a[i]==b[j])
            j++;
        if(j==lb)
        {
            printf("%d\n",i+1-lb+1);
            j=next[j-1];
        }
    }
    for(int i=0;i<lb;i++)
    {
        printf("%d ",next[i]);
    }
    printf("\n");
    return 0;
} 
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注