P8630 [蓝桥杯 2015 国 B] 密文搜索

P8630 [蓝桥杯 2015 国 B] 密文搜索 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P8630

题目分析

        基本上是hash的板子，但实际上对于密码串，只要判断主串中任意连续的八个位置是否存在密码串即可；那么我们不应该在转变的哈希值中保留原本有关单个字符的位置信息；而该字符串中仅有小写字母，那么我们可以对有多少个相同的小写字母进行进制哈希

---

代码示例

#include 
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;
}