KMP完整版

ButterflyDew · 2018-04-26 22:02:45 · 个人记录

KMP算法

简介

Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。

一、暴力做法的损失

定义：称待匹配串（长串）为S1，匹配串（短串）为S2。n为S1长度，m为S2长度。

暴力做法：

枚举S1
S1已枚举到第i位，枚举S2，看以第i位为开头的S1与S2能否配对

最坏复杂度：O（N*M）

这样做，事实上我们损失了十分多的信息

比如说

S1="abababc"

S2="ababc"

在S1的第1位的时候，在第5号失配了，显然，这时候我们把S2的左边直接挪到第3位是最优的。

我们如何把损失的信息利用起来呢？

二、定义串的模式值NEXT

定义：next[i]代表S2在第i位（与S1的某一位）失配时，将自身跳转到next[i]位置继续进行匹配。
特别的，next[i]==-1代表S2在S1的某一位已经无法匹配，将匹配S1的下一位。

三、求串的模式值NEXT

求法:

(一). 若k==-1或者s[j-1]==s[k]

(1) 当前位j满足条件①且不满足条件②，next[j]=k+1

(2) 否则，next[j]=next[k+1]

(二). 令k=next[k]继续寻找边界

约定：

(1) next[0]=-1

(2) 约束条件①：在当前位j前面的字串（不包括j）中，存在s[0~k]=s[(j-k-1)~(j-1)]，k∈(0,j-1)，且k取最大值

(3) 约束条件②（是依托于①的）： S2[j]=S2[k+1]

看到这肯定一脸萌币（并没有暴露什么），没事下面有解释，对着上面看就知道为什么了（注意(一)(二)在最后面，所以哪怕觉得奇怪也要按顺序看哦）。
解释：

(1) 约束条件①：

感性理解：即为在j前面的子串中前缀与后缀相同两个串最长的那个

举例：

ABABAC

对C前面的ABABA，前缀ABA等于后缀ABA，k=2

(2) 约束条件②：

假设已满足约束条件①（否则无意义）

感想理解：在j加入j前面的子串后，前后缀相等的两个串延长了1位

举例：

ABABAB

对B（第三个）前面的ABABA,有S2[5]=S2[3],即第二个B等于了第三个B

(3) 约束条件的存在意义

假设已经S1匹配到第i位，S2匹配到第j位

（S1只是一个片段，S2的蓝色部位为相等的前后缀。）

假设此时i!=j（失配），我们应该跳到哪里比呢？

按照之前的做法我们要先比较一下j和k+1是否相等

㈠如果不相等

显然，i与k+1是否相等是不确定的，我们把S2挪到k+1

继续配对，即为next[j]=k+1

㈡如果相等呢？

这时候，我们将S2前面一个蓝色的块块放大，如S2^{'}

显然，i（在值上i=j=k+1）与k^{'}+1是否相等是不确定的,我们把S2挪到k^{'}+1继续配对，即为next[j]=next[k+1]

(4) 求法中(一)(二)大点的存在意义

为什么放在最后说，因为要确保已有的信息基础。

我们要求解next，要确保在j前面已经形成了前后缀相等的串，而s[j-1]==s[k]不就是前提条件吗？

四、参考代码

#include <cstdio>
using namespace std;
const int N=1000010;
char s1[N],s2[N];
int next[N],t[N];
int main()
{
    freopen("KMP.in","r",stdin);
    freopen("KMP.out","w",stdout);
    char c=getchar();
    int len1=-1,len2=-1;
    while(c!='\n')
    {
        s1[++len1]=c;
        c=getchar();
    }
    c=getchar();
    while(c!='\n')
    {
        s2[++len2]=c;
        c=getchar();
    }
    int k=-1,j=0;
    next[0]=-1;
    while(j<=len2)
    {
        if(k==-1||s2[k]==s2[j])
        {
            k++,j++;
            if(s2[k]!=s2[j])
                next[j]=k;
            else
                next[j]=next[k];
        }
        else
            k=next[k];
    }
    k=0,j=0;
    int cnt=0;
    while(j<=len1)
    {
        while(k!=-1&&s1[j]!=s2[k])
            k=next[k];
        if(k==len2)
            t[++cnt]=j,k=next[k]==-1?0:next[k];
        else
            j++,k++;
    }
    for(int i=1;i<=cnt;i++)
        printf("%d ",t[i]+1-len2);
    return 0;
}

2018.4.27