KMP算法详解&&P3375 【模板】KMP字符串匹配题解

KMP算法详解:

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt(雾)提出的。

对于字符串匹配问题(such as 问你在abababb中有多少个ab串?),朴素的想法是定一个i,从字符串首扫到字符串尾部来枚举字符串位置,找到一个首字符相同的就通过第二层for循环来继续往下一个字符一个字符的匹配。

直到匹配到长度和需要匹配的子串(模式串)长度相等,我们就说找到了一个在原串中的子串并将答案加一,然后继续往下像蜗牛一样的搜索。

有关相似的算法,链接这里hash

举个栗子:A:GCAKIOI      B:GC     ,那么我们称B串是A串的子串

我们称等待匹配的A串为主串,用来匹配的B串为模式串。

一般的朴素做法就是枚举B串的第一个字母在A串中出现的位置并判断是否适合,而这种做法的时间复杂度是O(mn)的,当你处理一篇较长文章的时候显然就会超时。

我们会发现在字符串匹配的过程中,绝大多数的尝试都会失败,那么有没有一种算法能够利用这些失败的信息呢?

KMP算法就是

KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的

设主串(以下称为T)

设模式串(以下称为W)

用暴力算法匹配字符串过程中,我们会把T[0] 跟 W[0] 匹配,如果相同则匹配下一个字符,直到出现不相同的情况,此时我们会丢弃前面的匹配信息,然后把T[1] 跟 W[0]匹配,循环进行,直到主串结束,或者出现匹配成功的情况。这种丢弃前面的匹配信息的方法,极大地降低了匹配效率。

我们来看一看KMP是怎么工作的

在KMP算法中,对于每一个模式串我们会事先计算出模式串的内部匹配信息(也就是说这个东西只和模式串有关,可以预处理,这个处理我们后面会提到),在匹配失败时最大的移动模式串,以减少匹配次数。

比如,在简单的一次匹配失败后,我们会想将模式串尽量的右移和主串进行匹配。右移的距离在KMP算法中是如此计算的:在已经匹配的模式串子串中,找出最长的相同的前缀和后缀,然后移动使它们重叠。

我们用两个指针i和j分别表示A[i-j+1......i]和B[1......j]完全相等,也就是说i是不断增加的,并且随着i的增加,j也相应的变化,并且j满足以A[j]结尾的长度为j的字符串正好匹配B串的前j个字符,现在需要看A[i+1]和B[j+1]的关系

  • 当A[i+1]=B[j+1]时,我们将i和j各增加1
  • 否则,我们减小j的值,使得A[i-j+1......i]和B[1......j]保持匹配并尝试匹配新的A[i+1]和B[j+1]

举个栗子:

T: a b a b a b a a b a b a c b

W:a b a b a c b

当i=j=5时,此时T[6]!=W[6],这表明此时j不能等于5了,这个时候我们要改变j的值,使得W[1...j]中的前j'个字母与后j'个字母相同,因为这样j变成j'后(也就是将W右移j'个长度)才能继续保持i和j的性质。这个j'显然越大越好。在这里W[1...5]是匹配的,我们发现当ababa的前三个字母和后三个字母都是aba,所以j'最大也就是3,此时情况是这样

T: a b a b a b a a b a b a c b

W:      a b a b a c b

那么此时i=5,j=3,我们又发现T[6]与W[4]是相等的,然后T[7]与W[5]是相等的(这里是两步)

所以现在是这种情况:i=7,j=5

T: a b a b a b a a b a b a c b

W:      a b a b a c b

这个时候又出现了T[8]!=W[6]的情况,于是我们继续操作。由于刚才已经求出来了当j=5时,j'=3,所以我们就可以直接用了(通过这里我们也可以发现j'是多少和主串没有什么关系,只和模式串有关系)

于是又变成了这样

T: a b a b a b a a b a b a c b

W:            a b a b a c b

这时,新的j=3依然不能满足A[i+1]=B[j+1],所以我们还需要取j'

我们发现当j=3时aba的第一个字母和最后一个字母都是a,所以这时j'=1

新的情况:

T: a b a b a b a a b a b a c b

W:                  a b a b a c b

仍然不满足,这样的话j需要减小到j'就是0(我们规定当j=1时,j'=0)

T: a b a b a b a a b a b a c b

W:                     a b a b a c b

终于,T[8]=B[1],i变为8,j变为1,我们一位一位往后,发现都是相等的,最后当j=7还满足条件时,我们就可以下结论:W是T的子串,并且还可以找到子串在主串中的位置(i+1-m+1,因为下标从0开始)

这一部分的代码其实很短,因为用了for循环

inline void kmp()
{
int j=;
for(int i=;i<n;i++)
{
while(j>&&b[j+]!=a[i+]) j=nxt[j];
if(b[j+]==a[i+]) j++;
if(j==m)
{
printf("%d\n",i+-m+);
j=nxt[j];
//当输出第一个位置时 直接break掉
//当输出所有位置时 j=nxt[j];
//当输出区间不重叠的位置时 j=0
}
}
}

这里就有一个问题:为什么时间复杂度是线性的?

我们从上述的j值入手,因为每执行一次while循环都会使j值减小(但不能到负数),之后j最多+1,因此整个过程中最多加了n个1.于是j最多只有n个机会减小。这告诉我们,while循环最多执行了n次,时间复杂度平摊到for循环上后,一次for循环的复杂度是O(1),那么总的时间复杂度就是O(n)的(n是主串长度)。这样的分析对于下文的预处理来说同样有效,也可以得到预处理的时间复杂度是O(m)(m是模式串长度)

接下来是预处理

预处理并不需要按照定义写成O(m2)甚至O(m3),窝们可以通过nxt[1],nxt[2]....nxt[n-1]来求得nxt[n]的值

举个栗子

W :a b a b a c b

nxt:0 0 1 2 ??

假如我们有一个串,并且已经知道了nxt[1~4]那么如何求nxt[5]和nxt[6]呢?

我们发现,由于nxt[4]=2,所以w[1~2]=w[3~4],求nxt[5]的时候,我们发现w[3]=w[5],也就是说我们可以在原来的基础上+1,从而得到更长的相同前后缀,此时nxt[5]=nxt[4]+1=3

W :a b a b a c b

nxt:0 0 1 2 3?

那么nxt[6]是否也是nxt[5]+1呢?显然不是,因为w[nxt[5]+1]!=w[6],那么此时我们可以考虑退一步,看看nxt[6]是否可以由nxe[5]的情况所包含的子串得到,即是否nxt[6]=nxt[nxt[5]]+1?

事实上,这样一直推下去也不行,于是我们知道nxt[6]=0

那么预处理的代码就是这样的

inline void pre()
{
nxt[]=;//定义nxt[1]=0
int j=;
rep(i,,m-)
{
while(j>&&b[j+]!=b[i+]) j=nxt[j];
//不能继续匹配并且j还没有减到0,就退一步
if(b[j+]==b[i+]) j++;
//如果能匹配,就j++
nxt[i+]=j;//给下一个赋值
}
}

全部代码:

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
char s1[],s2[];
int p[];
int n,m;
inline void yuchuli()
{
int j=;
for(int i=;i<m;i++)
{
while(j>&&s2[i+]!=s2[j+])j=p[j];
if(s2[i+]==s2[j+])j++;
p[i+]=j;
}
}
int main(){
scanf("%s",s1+);scanf("%s",s2+);
n=strlen(s1+);m=strlen(s2+);
yuchuli();
int j=;
for(int i=;i<n;i++)
{
while(j>&&s1[i+]!=s2[j+])j=p[j];
if(s2[j+]==s1[i+])j++;
if(j==m)
{
printf("%d\n",i+-j);
j=p[j];
}
}
for(int i=;i<=m;i++)
{
printf("%d ",p[i]);
}
return ;
}

完结!

部分(后半段)内容引用ych大佬的

原因链接

上一篇:golang中,map作为函数参数是如何传递的


下一篇:集合之HashMap 与 HashSet