《ybtoj高效进阶》第二部分第三章例题1 子串查找

题目大意

KMP求匹配串在模式串中出现的次数。

思路

KMP板子不解释。
code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
int p[1000006],n,m,ans;
string a,b;
inline void f()
{
	p[1]=0;
	int i=1,j=0;
	while (i<m)
	{
		while (j&&b[1+j]!=b[1+i]) j=p[j];
		if (b[1+j]==b[1+i]) j++;
		p[i+1]=j;
		i++;
	}
	return;
}
inline void kmp()
{
	int i=0,j=0;
	while (i<n)
	{
		while (j&&b[1+j]!=a[1+i]) j=p[j];
		if (b[1+j]==a[1+i]) j++;
		if (j==m)
		{
			ans++;
			j=p[j];
		}
		i++;
	}
	return;
}
int main()
{
	cin>>a>>b;
	n=a.size(),m=b.size();
	a.insert(0," ");
	b.insert(0," ");
	f();
	kmp();
	cout<<ans;
    return 0;
}

最后

以上就是平淡魔镜为你收集整理的《ybtoj高效进阶》第二部分第三章例题1 子串查找的全部内容，希望文章能够帮你解决《ybtoj高效进阶》第二部分第三章例题1 子串查找所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。