KMP 模式串匹配 失去匹配的瞬间你还有什么

KMP:

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。

——百度百科。

自我理解:

kmp算法最最最最核心的思想,就是在每一次失去匹配的时候,找到最大的可能能够匹配的子段进行匹配。

也就是著名的nxt数组。

算法流程:

数组只介绍一个nxt数组。nxt[i]表示,从1~i前缀S中,最长的前缀等于后缀的长度(不能是S)。

在每次失去匹配的时候,因为上次已经能够匹配到j了,所以1~j和 i-j~i-1 是相等的。

所以我们让j=nxt[j]的时候,根据定义,1~nxt[j] = j-nxt[j]+1~j , 又因为:1~j = i-j~i-1 所以 j-nxt[j]+1 ~ j = i-nxt[j] ~ i-1

这样,我们退一步到nxt,可以找到失去匹配后,最大的可能再次匹配上的字段长度nxt[j]

代码实现:

void kmp(){
nxt[]=;
for(int i=,j=;i<=l2;i++){
while(j>&&b[i]!=b[j+]) j=nxt[j];
if(b[i]==b[j+]) j++;
nxt[i]=j;
}
}

下面这里还加上了f数组,f[i]表示,在a串中,以第i位结尾的所有子串,和b串的前缀最大匹配的长度。

转移是类似的。

void fin(){
for(int i=,j=;i<=l1;i++){
while(j>&&(j==l2||a[i]!=b[j+])) j=nxt[j];
if(a[i]==b[j+]) j++;
f[i]=j;
if(f[i]==l2){
printf("%d\n",i-l2+);
}
}
}

这样就可以求出模式串在原始串中出现的位置和个数了。

应用:

1.模式串在主串中出现的次数。见上述代码。
2.求一个串的循环节:
长度为n的字符串的最短循环节是:n-nxt[n],(可以证明:1.可以循环 2.是最短的)

当n%(n-nxt[n])等于0的时候,字符串是一个循环字符串。最长循环次数为:n/(n-nxt[n])

应用例题:

T1:NOI2014 动物园

这个题考察S的前缀中,处理不重叠前缀等于后缀的数量。

可以先求出重叠的nxt[i],num1[]

在处理不重叠的num2[]的时候,跳nxt[j]的时候,跳跃不停止的条件加上一个2*j>i还要跳,因为不能重叠。

跳完后,判断能否加1,如果2*j>i再跳一次。(WA了。。。)

最后,num2[i]=num1[j]+1 注意,这里一定是num1,也就是可重叠的。因为2*j<=i,所以,j中重叠是没有关系的。(WA了。。。)

加一表示1~j和i-j+1~i也是一个。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=+;
const int mod=1e9+;
int nxt1[N],nxt2[N],num1[N],num2[N];//1: can 2: can't folded
char a[N];
int l;
ll ans;
void kmp1(){
nxt1[]=,num1[]=;
for(int i=,j=;i<=l;i++){
while(j&&a[i]!=a[j+]) j=nxt1[j];
if(a[i]==a[j+]) j++;
nxt1[i]=j;
if(nxt1[i]) num1[i]=num1[j]+;
}
}
void kmp2(){
nxt2[]=;num2[]=;
for(int i=,j=;i<=l;i++){
while(j&&(*j>i||a[i]!=a[j+])) j=nxt1[j];//warning!!
if(a[i]==a[j+]) j++;
if(*j>i) j=nxt1[j];//warning!!
nxt2[i]=j;
if(nxt2[i]) num2[i]=num1[j]+;
}
}
int main()
{
int n;
scanf("%d",&n);
while(n--){
scanf("%s",a+);
ans=;
l=strlen(a+);
kmp1();
kmp2();
for(int i=;i<=l;i++){
ans=(ans*((ll)+num2[i]))%mod;
}
printf("%lld\n",ans);
memset(num1,,sizeof num1);
memset(num2,,sizeof num2);
}
return ;
}

动物园

T2:bzoj4641 基因改造

上一篇:centos下tomcat启动卡死


下一篇:ubuntu安装nvidia显卡驱动