首页 / 算法 / 【模版】字符串匹配 KMP 算法
【模版】字符串匹配 KMP 算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【模版】字符串匹配 KMP 算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2562字,纯文字阅读大概需要4分钟。
内容图文
![【模版】字符串匹配 KMP 算法](/upload/InfoBanner/zyjiaocheng/643/4107f005f6b84597953ba4adb9232cc1.jpg)
字符串匹配KMP算法
给出两个字符串 S1? 和 S2? ,其中 S2? 为 S1? 的子串.
1. 求出 S2? 在 S1?中所有出现的位置.
2. 输出子串的前缀数组 nxt[i].
先引入两个概念(通俗解释):
模式串:要查找的字符串。(即 S2? )
文本串:被用来查找模式串的字符串。 (即 S1? )
将模式串与文本串做匹配时,若用传统的从头到尾匹配法,复杂度 O(N+M) 到 O(N?M) 不等。考虑用奇怪的玄学方法优化。
如果 模式串匹配到最后几位了,发现出现了失配,那么全面放弃还是挺可惜的,毕竟前边匹配了那么多。如果当前的模式串前面出现了 一个真子集,与该模式串前缀相同,那么该前缀可以向前移动过来啊,这一部分也一定匹配的。也就是说,将模式串整体向前移动也若干位,因为我们通过前缀移动自动匹配的,我们保证其匹配。
比如:
模式串: ABCABCD
文本串: ABCABCABCD
匹配前六个字符时成功,但是第七位不成功,但发现第 1、2、3 位字符与第 4、5、6 位字符相同,那么我们可以把前三位字符向前推进三位,然后再往后推进。这样就得到了优化。问题在于,当第七位失配时,如何确定第六位应该对应前边第几位呢,从这个样例来看,显然是第三位,所以引入 nxt[i] 数组,表示 在模式串第 i 位失配时,应该退回到 nxt[i] 位,再次向后匹配。所以我们应该预处理 nxt[i] 数组。
所以上边样例的 nxt[i] 的值(从下标 1 开始): 0、0、0、1、2、3、0
预处理方法如图所示:
int p = 0;
for(int i = 2; i <= len2; i++)
{
while(p && s2[i] != s2[p+1]) p = nxt[p];
if(s2[p+1] == s2[i]) p++;
nxt[i] = p;
}
那么与文本串匹配时的书写,如下所示:
p = 0;
for(int i = 1; i <= len1; i++)
{
while(p && s2[p+1] != s1[i]) p = nxt[p];
if(s2[p+1] == s1[i]) p++;
if(p == len2)
{
printf("%d\n",i-len2+1);
p = nxt[p];
}
}
还没做练习题,待学完AC自动机后再补题补坑吧(2020年2月21日 14:12:40)
完整代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
char s1[1001000],s2[1000100];
int nxt[1001000];
int main()
{
scanf("%s%s",s1+1,s2+1);
int len1 = strlen(s1+1), len2 = strlen(s2+1);
int p = 0;
for(int i = 2; i <= len2; i++)
{
while(p && s2[i] != s2[p+1]) p = nxt[p];
if(s2[p+1] == s2[i]) p++;
nxt[i] = p;
}
p = 0;
for(int i = 1; i <= len1; i++)
{
while(p && s2[p+1] != s1[i]) p = nxt[p];
if(s2[p+1] == s1[i]) p++;
if(p == len2)
{
printf("%d\n",i-len2+1);
p = nxt[p];
}
}
for(int i = 1; i <= len2; i++)
printf("%d ",nxt[i]);
system("pause");
return 0;
}
例题:[模版]KMP算法
oier991215 发布了12 篇原创文章 · 获赞 12 · 访问量 1198 私信 关注内容总结
以上是互联网集市为您收集整理的【模版】字符串匹配 KMP 算法全部内容,希望文章能够帮你解决【模版】字符串匹配 KMP 算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。