烟台网站制作专业,wordpress弹出式视频,网络营销案例分析200字,网站建设与开发学习引例
题目描述
给定一个字符串 A A A 和一个字符串 B B B#xff0c;求 B B B 在 A A A 中的出现次数。 A A A 和 B B B 中的字符均为英语大写字母或小写字母。 A A A 中不同位置出现的 B B B 可重叠。
输入格式
输入共两行#xff0c;分别是字符串 A A A 和字符串…引例
题目描述
给定一个字符串 A A A 和一个字符串 B B B求 B B B 在 A A A 中的出现次数。 A A A 和 B B B 中的字符均为英语大写字母或小写字母。 A A A 中不同位置出现的 B B B 可重叠。
输入格式
输入共两行分别是字符串 A A A 和字符串 B B B。
输出格式
输出一个整数表示 B B B 在 A A A 中的出现次数。
样例输入
zyzyzyz
zyz样例输出
3数据范围与提示 1 ≤ A , B 1 \leq A, B 1≤A,B 的长度 ≤ 1 0 6 \leq 10 ^ 6 ≤106 A A A、 B B B 仅包含大小写字母。
暴力求解思路
逐一枚举 A A A 中的位置 i i i 作为 B B B 的起点检查是否可以匹配时间复杂度为 O(n2)显然会超时。
一、进制
通过对各种进制的观察我们不难发现
任意一个 R R R 进制的数都可以看成是一个满足如下条件的字符串 每个位上都是 [ 0 , R − 1 ] [0, R-1] [0,R−1] 之间的一个数字两个字符串相等当且仅当这两个字符串代表的 R R R 进制数相等。 判断两个字符串相等需要一层循环是 O(n) 的而判断两个数相等是 O(1) 的。所有英文字母的取值范围都在 128 以内因此每个英文字母均可以看成是一个 R ( R 128 ) R(R128) R(R128) 进制数的基数值任意一个字符串均可看作有一个或多个位的 R R R 进制数。 H ( a b c d ) 97 ⋅ R 3 98 ⋅ R 2 99 ⋅ R 100 H ( a b ) 97 ⋅ R 98 H ( c d ) 99 ⋅ R 100 H ( a b c d ) − H ( a b ) ⋅ R 2 \begin{aligned} H(abcd) 97\cdot R^398\cdot R^299\cdot R100 \\ H(ab) 97\cdot R98 \\ H(cd) 99\cdot R100H(abcd)-H(ab)\cdot R^2 \end{aligned} H(abcd)H(ab)H(cd)97⋅R398⋅R299⋅R10097⋅R9899⋅R100H(abcd)−H(ab)⋅R2 不难看出在已知某个字符串的所有前缀的 R R R 进制数值的前提下计算任意一个子串的 R R R 进制数值只需 O(1) 的时间当然还需要预处理出 R i R^i Ri 的值。
至此对于上面的题目我们可以
把 B B B 转为一个 R R R 进制数 h b hb hb时间复杂度为 O(n)。逐一枚举 A A A 中的位置 i i i预处理出 A A A 的前 i i i 位构成的 R R R 进制数的数值 h [ i ] h[i] h[i]时间复杂度为 O(n)。逐一枚举 A A A 中的位置 i i i用 O(1) 的时间 A A A 中从第 i i i 个位开始的与 B B B 相同的一个字符串对应的 R R R 进制数 h a ha ha检查是否满足 h b h a hbha hbha。
按照这个思路整个算法的时间复杂度就降到了 O(n)可以通过了。
但是等等这里好像有一个问题由于 R R R 是大于等于 128 的数 R i R^i Ri 很容易就会超出 i n t int int 甚至 l o n g l o n g long\ long long long 的取值范围我们根本无法存储。而如果采用大整数来运算及存储就得不偿失了。
那该怎么办呢
我们遇到了一个取值范围远大于表示范围的对应问题就如同关键字与位置下标的对应问题要将取值范围非常大的一组数字符串的 R R R 进制数值尽量没有冲突地均匀存入一个空间有限的数组基础变量类型的取值范围中这是标准的散列问题。
二、散列
设计这种散列函数一定要简单且快通常采用经典的“除留余数法”为了减少冲突我们需要做 2 件事情
要让余数的取值范围尽量大采用最大的数据类型 unsigned long long相当于模 264。 R R R 选取一个大于 128 的素数例如131,13331 等等。 H ( a b c d ) 97 × 13 1 3 98 × 13 1 2 99 × 131 100 218064827 1681778 12969 100 219746605 \begin{aligned} H(abcd) 97\times 131^398\times 131^299\times 131100\\ 218064827168177812969100\\ 219746605 \end{aligned} H(abcd)97×131398×131299×131100218064827168177812969100219746605 那么上面为什么没有去模 264 呢因为 unsigned long long 本身恰好就是 64 位它计算出来的结果本来就是只保留小于 264 的部分这称作自然溢出。
好啦到此为止我们就完成了真个算法设计看看代码吧
#include iostream
#include cstring
using namespace std;
using ULL unsigned long long;
const int N 1e6 7, P 131;
ULL sum[N], sa, pw[N];
char s[N];
int main() {scanf(%s, s 1);pw[0] 1;int len strlen(s 1);for (int i 1; s[i]; i) {sum[i] sum[i-1] * P s[i];pw[i] pw[i-1] * P;}scanf(%s, s 1);int lena strlen(s 1), ans 0;for (int i 1; s[i]; i)sa sa * P s[i];for (int i 1; ilena-1 len; i) {ULL d sum[ilena-1] - sum[i-1]*pw[lena];if (d sa) ans;}printf(%d, ans);return 0;
}
相关文章：
