KMP算法与其应用

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了KMP算法与其应用，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1540字，纯文字阅读大概需要3分钟。

内容图文

KMP字符串匹配

题目链接：https://www.luogu.org/problemnew/show/P3375

1.nxt数组：

nxt[x]：以x位结尾的字符串为后缀能匹配到的最长前缀。

求法见代码:

nxt[1]=0;int j=0;
	for(int i=2;i<=n2;i++)
	{
		while(j&&s2[j+1]!=s2[i]) j=nxt[j];//这里是一个找最长前缀的过程 
		if(s2[j+1]==s2[i]) j++;
		nxt[i]=j;
	}

然后要匹配s1和s2。其实和求nxt的方法是一样的呢。注意f[i]：i结尾的几位和s2前几位相同（最长前缀）

这里注意f[i]==n2时就是匹配成功啦

j=0;
	for(int i=1;i<=n1;i++)//f[i]：i结尾的几位和s2前几位相同 
	{
		while(j&&s2[j+1]!=s1[i]) j=nxt[j];
		if(s2[j+1]==s1[i]) j++;
		f[i]=j;
	}
	for(int i=1;i<=n1;i++) if(f[i]==n2) cout<<i-n2+1<<endl;
	for(int i=1;i<=n2;i++) cout<<nxt[i]<<" ";
	cout<<endl;

KMP求最长周期：

题目链接：https://www.luogu.org/problemnew/show/P3435

这里首先要搞清楚周期的定义！

最短周期：串长-最长相同前后缀长

最长周期：串长-最短相同前后缀长

因为这题是求最长周期，所以要知道最短相同前后缀长。但我们的nxt数组求得是最长相同前后缀长，那怎么办呢？

不急，我们试着考虑对于每一个串它的最短后缀长一定包含在最长后缀长之中：所以不断的找nxt，直到找到最短的非零的那个就好啦。这里运用一个技巧：从头往后枚举，nxt[i]直接就等于nxt[nxt[i]]（如果nxt[nxt[i]]不等于0的话）

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;
const int maxn=1000005;
char s[maxn];int nxt[maxn];
int main()
{
	int n;scanf("%d",&n);scanf("%s",(s+1));
	nxt[1]=0;int j=0;
	for(int i=2;i<=n;i++)
	{
		while(j&&s[j+1]!=s[i]) j=nxt[j];
		if(s[j+1]==s[i]) j++;
		nxt[i]=j;
	}
	for(int i=1;i<=n;i++)
	{
		if(nxt[nxt[i]]) nxt[i]=nxt[nxt[i]];	
	} 
	int ans=0;
	for(int i=1;i<=n;i++) if(nxt[i]) ans+=(i-nxt[i]);
	cout<<ans<<endl;
	return 0;
}

 

 

内容总结

以上是互联网集市为您收集整理的KMP算法与其应用全部内容，希望文章能够帮你解决KMP算法与其应用所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---