KMP 算法

摘要

用于字符串匹配,在 O(n) 复杂度内完成匹配。

算法思想

对于朴素算法,当 即匹配失败时,是将整个 S 向后移动一位,复杂度 O(mn)。这种算法的缺点在于,移动一位时会重复比较已比较的位置。

KMP 算法的想法是:设法利用已知信息,不要把 “搜索位置” 移回已经比较过的位置,而是继续把它向后移。

那么问题来了,究竟应该移多少位呢?
试想 S=ABCDABD ,T=ABCDCABCABCABD,比较情况如下:
- 表示成功匹配,^ 表示不匹配

ABCDABCDABDABD
ABCDABD
------^

可见 ABCDAB 是成功匹配。而第 7 位(1 起点)不匹配。如果直接移到第 8 位,则错过了第 5 位开始的匹配串。而将位于第 1 位的匹配串移动到第 5 位,理由是: ,同时 也是 的后缀,也是 S[1~6] 的前缀。

对于 S[i], 定义 表示最大的 使得 的后缀,也就是最长的

对于 S=ABCDABD,next[] 如下:

S     A B C D A B D
next  0 0 0 0 1 2 0

Next 的求法

next 的求法与 KMP 算法本身相似,思想是自己匹配自己。

假设我们已知 的值,求 .

此时定义 . 根据 可判断 的匹配情况:

  • 如果 , 则 ;
  • 否则,将 赋值为 ,继续循环比较,直到

模板

LuoguP3375【模板】KMP 字符串匹配

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;

char s1[N],s2[N];

void getnext(char *s,int * nex,int ls){//1 起点
    nex[1]=0;// 第一位失配
    for(int i=2,j=0;i<=ls;i++){while(j&&s[i]!=s[j+1])j=nex[j];
        if(s[i]==s[j+1])++j;
        nex[i]=j;
    }
}
int nex[N];
void kmp(char *s,int ls,char *t,int lt){getnext(s,nex,ls);
    for(int i=1,j=0;i<=lt;i++){while(j>0&&t[i]!=s[j+1])j=nex[j];
        if(t[i]==s[j+1])++j;
        if(j==ls)printf("%d\n",i-ls+1),j=nex[j];
    }
}
int main(){scanf("%s%s",s1+1,s2+1);
    int l1=strlen(s1+1),l2=strlen(s2+1);
    kmp(s2,l2,s1,l1);
    for(int i=1;i<=l2;i++)printf("%d",nex[i]);
    return 0;
}

Border

对一个串,其相等的前后缀是一组 border。而我们 KMP 算法其实就是在求,即 表示的是 的最长的 border。

循环串(周期)

对于一个长度为 的字符串 ,若存在一个前缀 满足 循环构成,且最后一个循环节是 的前缀(即最后的尾部不一定是完整的 ),那么称 是循环串,其循环节为 . 显然一个循环串可能有多个循环节。如果尾部循环节是完整的 ,那么 就是严格循环串。

对于一个循环串,其循环节与 border 是一一对应的。如图:

p1

那么判断一个串是否存在严格循环的循环节,用 next 指针判断 即可,这个结合 border 就能证明

border 的树形结构

在 KMP 中的 border 结合 next 指针,呈现一个树形的结构

p2

那么 KMP 显然可以求 border。利用树上倍增或者二分,可以对前缀 a 求 <=b 的最长 border


  转载请注明: Sshwy's Blog KMP 算法

 上一篇
字符串小结 字符串小结
KMP 复杂度的证明咕咕 一道题 给一个串, 支持插入删除最后面的字符, 求循环节的长度。这里的循环节是整个串的循环节,任意一个都可以. 求循环节就相当于求 Next 指针,考虑 Next 指针的构建过程。当前的 Next 指针是建立在
2019.02.12
下一篇 
金华自闭 Day1 金华自闭 Day1
A. 串20pts 暴力枚举 . 具体来说,我们先枚举 ,然后按等差数列枚举 ,check 一下统计即可 check 失败就 break 40pts其他人好像都是前缀和来着。。。 变换一下枚举顺
2019.02.11
  目录