【ybtoj 高效进阶 2.3】 【kmp】 子串查找

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【ybtoj 高效进阶 2.3】 【kmp】 子串查找，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含938字，纯文字阅读大概需要2分钟。

内容图文

【ybtoj 高效进阶 2.3】 【kmp】 子串查找

题目

---

解题思路

kmp模板题
kmp的策略是调整 k k k 点位置（减小 k k k 值）并使 k k k 值尽量大，使得 A A A[ i i i- j j j+1… i i i]= B B B[1… j j j] 保持匹配且尝试匹配 A A A[ i i i+1]与 B B B[ j j j+1]

板子

for (int i=1;i<=len1;i++)
	{
		while (k!=0&&x[i]!=y[k+1]) k=next[k];
		if (x[i]==y[k+1]) k++;
		if (k==len2) ans++;  
	}

手推过程解释
P . S P.S P.S n e x t next next是 B B B串和自己匹配出来的
就是板子里 x x x和 y y y是一样跑出来的

---

代码

#include<iostream> 
#include<cstring>
#include<cstdio>
using namespace std;
int len1,len2,ans;
int next[1000010]; 
char x[1000010],y[1000010];
int main()
{
	scanf("%s%s",x+1,y+1);
	len1=strlen(x+1); 
	len2=strlen(y+1);
	next[1]=0;
	int k=0;
	for (int i=2;i<=len2;i++)
	{ 
		while (k>0&&y[i]!=y[k+1]) k=next[k];
		if (y[i]==y[k+1]) k++;
		next[i]=k; 
	}  //B串自己匹配，求出next
	k=0;
	for (int i=1;i<=len1;i++)
	{
		while (k!=0&&x[i]!=y[k+1]) k=next[k];
		if (x[i]==y[k+1]) k++;
		if (k==len2) ans++;  //完全匹配，次数+1
	}  //A串和B串匹配
	printf("%d\n",ans);
	return 0;
}

内容总结

以上是互联网集市为您收集整理的【ybtoj 高效进阶 2.3】 【kmp】 子串查找全部内容，希望文章能够帮你解决【ybtoj 高效进阶 2.3】 【kmp】 子串查找所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

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

内容手机端

---