信息学奥赛一本通 1455：【例题1】Oulipo

本文主要是介绍信息学奥赛一本通 1455：【例题1】Oulipo，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

1455：【例题1】Oulipo

分析

数据范围比较大，直接枚举会爆掉，需要字符串哈希，哈希值相同则两个字符串相同。

哈希就不说了，这里简单描述过程：

设定P，一般为131或13331
设定模mod，一般取 $2^{32}$ 或 $2^{64}$ ，实际上用unsigned int或unsigned long long就可以，会自然溢出。
设xp数组，预处理 $P^i$ 。
设h数组，表示哈希值， $h_i=h_{i-1}\times P + str_i$ ，但字符串下标从1开始
$str_{l \cdots r}$ 的哈希值为 $h_r-h_{l-1}\times P^{r-l+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;
}

这篇关于信息学奥赛一本通 1455：【例题1】Oulipo的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！