P8630 [藍橋杯 2015 國 B] 密文搜索 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)
https://www.luogu.com.cn/problem/P8630
題目分析
? ? ? ? 基本上是hash的板子，但實際上對于密碼串，只要判斷主串中任意連續的八個位置是否存在密碼串即可；那么我們不應該在轉變的哈希值中保留原本有關單個字符的位置信息；而該字符串中僅有小寫字母，那么我們可以對有多少個相同的小寫字母進行進制哈希
代碼示例
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int base = 131;
const int N = 1e5 + 10;char s[N], s1[N];
ull t[140];//字母信息
ull a[N]; //主串的字串哈希值ull gets() {int hash = 1;for(int i = 'a'; i <= 'z'; i++) hash = hash * base + t[i];return hash;
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n; cin >> s >> n;int len = strlen(s);for(int i = 0; i <= len - 8; i++) { //計算各字串哈希值memset(t, 0, sizeof t);for(int j = i; j <= i + 7; j++) t[(int)s[j]]++; //存儲該字串字母個數a[i] = gets(); //存儲hash值}int ans = 0;while(n--) {memset(t, 0, sizeof t);cin >> s1;for(int i = 0; i <= 7; i++) t[(int)s1[i]]++;ull b = gets();for(int i = 0; i <= len - 8; i++) {if(b == a[i]) ans++;}}cout << ans << ' ';return 0;
}
