信息学奥赛一本通 1455:【例题1】Oulipo
2023-12-16 04:52:43
题目
分析
数据范围比较大,直接枚举会爆掉,需要字符串哈希,哈希值相同则两个字符串相同。
哈希就不说了,这里简单描述过程:
- 设定P,一般为131或13331
- 设定模mod,一般取或,实际上用unsigned int或unsigned long long就可以,会自然溢出。
- 设xp数组,预处理。
- 设h数组,表示哈希值,,但字符串下标从1开始
- 的哈希值为
这里只要开一个h就行,s1的哈希值用一个变量递推就可以。
代码
#include <iostream>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
const int N = 1e6 + 14, P = 131;
char s1[N], s2[N];
ull xp[N], h[N];
ull get(int l, int r) {
return h[r] - h[l - 1] * xp[r - l + 1];
}
int main() {
// 预处理p的i次方
xp[0] = 1;
for (int i = 1; i < N; i++) xp[i] = xp[i - 1] * P;
int kase;
cin >> kase;
while (kase--) {
// 输入,下标从1开始
cin >> s1 + 1 >> s2 + 1;
int len1 = strlen(s1 + 1), len2 = strlen(s2 + 1), cnt = 0;
memset(h, 0, sizeof h);
// 处理s1的哈希值
ull q = 0;
for (int i = 1; i <= len1; i++) q = q * P + s1[i];
// 处理s2的哈希值
for (int i = 1; i <= len2; i++) h[i] = h[i - 1] * P + s2[i];
// 匹配
for (int i = 1; (i + len1 - 1) <= len2; i++)
if (get(i, i + len1 - 1) == q) cnt++;
cout << cnt << endl;
}
return 0;
}
文章来源:https://blog.csdn.net/sblsf/article/details/135025936
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!