#103. 子串查找

题目描述：
这是一道模板题。

给定一个字符串 A 和一个字符串 B，求 B 在 A 中的出现次数。A 和 B 中的字符均为英语大写字母或小写字母。
A中不同位置出现的 B 可重叠。

输入格式:
输入共两行，分别是字符串 A 和字符串 B。

输出格式:
输出一个整数，表示 B 在 A 中的出现次数。

样例输入:

zyzyzyz
zyz

样例输出:

3

数据范围与提示:

1<=A,B的长度<=10^6，A,B仅包含大小写字母

解析：
利用字符串哈希解题，将字符串看成b进制的数字，将其转换成十进制，先求出模式串的哈希值，然后依次求出主串前缀的哈希值，最后遍历长度为模式串长度的子串，若其哈希值等于模式串的哈希值，则结果加一；
特别注意的是，对于主串各子串的哈希值为 y[i]-y[i-l2]*pow，其中y为储存主串哈希值的数组，l2为模式串的长度，pow为l2个b的积；

代码：

#include"stdio.h"
#include"string.h"
#include"algorithm"
using namespace std;
char s1[1000010],s2[1000010];
unsigned long long x=0,y[1000010],pow=1;
int main()
{
	int i,l1,l2,b=501,sum=0;
	scanf("%s",s1);
	getchar();
	scanf("%s",s2);
	l1=strlen(s1);
	l2=strlen(s2);
	for(i=0;i<l2;i++)//计算模式串的哈希值
	{
		x=x*b+(unsigned long long)s2[i];
		pow=pow*b;计算pow
	}
	y[0]=s1[0];
	for(i=1;i<l1;i++)//计算主串各前缀的哈希值
	{
		y[i]=y[i-1]*b+(unsigned long long)s1[i];
	}
	for(i=l2-1;i<l1;i++)
	{
		if(i-l2>=0&&y[i]-y[i-l2]*pow==x)
		sum++;
		else if(i-l2<0&&y[i]==x)
		sum++;
	}
	printf("%dn",sum);
	return 0;
}

最后

以上就是大力奇异果为你收集整理的#103. 子串查找的全部内容，希望文章能够帮你解决#103. 子串查找所遇到的程序开发问题。

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