KMP算法

· · 算法·理论

KMP

一、KMP算法的理解：

KMP算法由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作，简称KMP。

KMP的基础用法是比对两个字符串，一母串一模式串，进行比对匹配，确定模式串是否为母串的子串。

在暴力做法中，我们会从母串的每个字符开始向后一个一个比对母串的字符和模式串的字符,

string mom,son;
bool y=0;
for(int i=0;i<mom.length();i++){
    bool v=1;
    for(int j=0;j<son.length();j++){
        if(mom[i+j]!=son[j]){
            v=0;break;
        }
    }
    if(v){
        y=1;break;
    }   
}
if(y)   printf("Yes");
else    printf("No");

这样的时间复杂度为O(mum.length()*son.length()),面对超长字符串时是毫无可行性的。

那么，我们希望可以尽可能的降低时间复杂度，在整个过程中，当母串与模式串比对到中间时，如果下一字符无法匹配，我们会将模式串后移一个从头比对匹配， 现在我想尽可能把模式串多后移几位，那么假如模式串还有特殊结构，时间复杂度将有效降低。

比如说，son有相同的前缀子串和后缀子串，

mom=abxabxabcabcxac
son=abxabc

在第一遍比对中，

      !
   abxabxabcabcxac
   abxabc
      i

发现 mom(abxab)=son(abxab) ，但 mom(x)!=son(c) , 所以要后移，同时发现son中此时有相同的前缀后缀子串 ab,所以后移三位,

      !
   abxabxabcabcxac
      abxabc
      i

字符串越长，如此操作省下的时间越多。如果经上述判断后，仍然不匹配，那就只能后移一位，然后重复上述操作。其实发现，省去的是对遍历模式串的时间。

字符串越长，模式串可能出现的前缀后缀越多，所以针对每对前后缀都应有记录，这样可以保证在不漏掉所有有可能的情况的同时，降低时间复杂度。

以上便是KMP的核心思想。

二、KMP的程序实现：

初始化

const int N=1000010;
int next[N];
string mom,son;
cin>>mom>>son;

next[ ]

在实现母串和模式串的匹配之前，要先确定模式串的前后缀记录，用 next[10^9] 来记录，表示：

对于模式串的1~j的子串，其有相同后缀的最长前缀终点下标为next[j]。

那么对于1~j的子串的次前后缀，前缀的终点下标为 next[next[j]] 。

模拟一下，

    1 2 3 4 5 6 7 8 9 
son=a b c a b c c a b
j=0

next[1]:  a:无缀（缀不能是串本身）                  next[1]=j=0    
next[2]:  a b:son[2]!=son[j+1] j=0 无               next[2]=j=0 
next[3]:  a b c:son[3]!=son[j+1] j=0 无             next[3]=j=0 
next[4]:  a b c a:son[4]==son[j+1] j++              next[4]=j=1
next[5]:  a b c a b:son[5]==son[j+1] j++            next[5]=j=2
next[6]:  a b c a b c:son[6]==son[j+1] j++          next[6]=j=3
next[7]:  a b c a b c c:son[7]!=son[j+1] j=next[j]
                        son[7]!=son[j+1] j=0        next[7]=j=0
next[8]:  a b c a b c c a:son[8]==son[j+1] j++      next[8]=j=1
next[9]:  a b c a b c c a b:son[9]==son[j+1] j++    next[9]=j=2

话不投机半句多，上代码。

#include<bits/stdc++.h>
using namespace std;
const int N = 1000100;
char m[N],s[N];
int ne[N];
int main(){
    scanf("%s\n%s",m+1,s+1);
    int lm=strlen(m+1),ls=strlen(s+1);
    ne[1]=0;
    for(int i=2,j=0;i<=ls;i++){
        while(j>0 && s[i]!=s[j+1])  j=ne[j];
        if(s[i]==s[j+1])    j++;
        ne[i]=j;
    }
    for(int i=1,j=0;i<=lm;i++){
        while(j>0 && m[i]!=s[j+1])  j=ne[j];
        if(m[i]==s[j+1])    j++;
        if(ls==j){
            printf("%d\n",i-ls+1);
            j=ne[j];
        }
    }
    for(int i=1;i<=ls;i++)
        printf("%d ",ne[i]);
    return 0;
}