首页 > 其他 > 详细

KMP

时间:2020-01-19 21:33:33      阅读:82      评论:0      收藏:0      [点我收藏+]

洛谷P3375:https://www.luogu.com.cn/problem/P3375

Knuth-Morris-Pratt字符串查找算法(简称为KMP算法)可在一个主文本字符串S内查找一个词W的出现位置。

KMP算法的作用是高效解决字符串匹配问题;

一般用暴力的方法解决字符串匹配问题是这样的

技术分享图片

 

 

 这个例子里我们可以看出第一次匹配失败第二次可以右移4位,而不是暴力算法的一位。也就是说这些步骤是没有意义的。我们想要优化就可以从这里入手。

我们可以判断出右移4位是因为前面的AB可以直接移到后面的AB处,这里就可以引进前缀后缀。仔细想一想,我们要移动的位数就是现在重合部分减去最长公共前后缀。

有了思想之后就要想怎么用代码实现了。

我们先要用nextt数组记录模板字符串从第一位到第i位的最长公共前后缀的长度。

如何记录呢,代码如下

技术分享图片

 

 重点注意i从2开始,nextt[1]=0。为什么呢,读者可以试一试从1开始然后输出nextt数组。

然后这段代码最重要的部分就是while那一行了。这也是比较难理解的地方。

每次匹配i和j+1.如果j+1不匹配,就跳到next[j]。第一次跳,匹配next[j]+1,再跳,就匹配next[next[j]] + 1.一直到j=0或者匹配成功。

此过程相当于模式串的自我匹配,所以不断的递归j = nextt[j],直到要么找到长度更短的相同前缀后缀,要么没有长度更短的相同前缀后缀

 

本人描述水平不佳,建议画图理解。

找到nextt数组后再进行比较。

技术分享图片

 

 while的过程和上面求nextt数组一样。

if(j==s2_l)是匹配的情况,后面可以进行一些操作,根据题目而定。此处是记录在文本字符串中匹配的位置。

其实我们可以发现这两个主要的过程差不多。

KMP算法就是对模板字符串自己进行一次匹配操作,然后再对文本字符串进行一次匹配操作。

完整代码如下

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
char s1[1000001],s2[1000001];
int nextt[1000001],s1_l,s2_l,ans[1000001],t=0;
void KMP(char *str)
{
 memset(nextt,0,sizeof(nextt));
 int j=0;
 for(int i=2;i<=s2_l;i++)
 {
  while(j&&str[j+1]!=str[i]) j=nextt[j];
  if(str[j+1]==str[i]) j++;
  nextt[i]=j;
 }
}
int main()
{
 //cin>>s1;
 scanf("%s%s",s1+1,s2+1);
 s1_l=strlen(s1+1);s2_l=strlen(s2+1);
 KMP(s2);
 int j=0;
 for(int i=1;i<=s1_l;i++)
 {
  while(j&&s2[j+1]!=s1[i]) j=nextt[j];
  if(s2[j+1]==s1[i]) j++;
  if(j==s2_l)
  {
   ans[++t]=i-s2_l+1;
   }
 }
 for(int i=1;i<=t;i++)
  printf("%d\n",ans[i]);
 for(int i=1;i<=s2_l;i++) printf("%d ",nextt[i]);
 return 0;
 }
 

KMP

原文:https://www.cnblogs.com/xcsj/p/12215589.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!