[CCPC陕西省赛2022 D题] Hash

题目描述

给定一个字符串 \(S\) ，按照如下方法获取 \(S\) 的哈希值：

//Language C++14
long long mod=5999993;
long long gethas(string s)
{
    long long ret=0;
    for (char c:s)
    ret=(ret*29+(c-'a'+1))%mod;
    return ret;
}

找到一个字符串 \(T\) ，使得 \(T\) 满足以下条件：

1. \(T\) 只包括小写字母
2. \(S\) 是 \(T\) 的前缀
3. \(S\) 和 \(T\) 的哈希值相同
4. \(1 \leq |T|-|S| \leq 50\)，\(|S|\) 标识 \(S\) 的长度

输入格式

第一行包括一个整数 \(T(1 \leq T \leq 1000)\) 。

接下来 \(T\) 行，每行一个字符串 \(S(1 \leq |S| \leq 100)\)。且 \(S\) 只包括小写字母。

输出格式

对于每个用例，输出一行一个字符串 \(T\) 表示答案。

题解

对于每个用例，额外构造的字符串的长度都不会超过 \(50\) ,故可以枚举额外构造的字符串长度，寻找是否有 \(hash(S) + mod \times k\) 落在该长度区间内即可。注意此题的特殊性在于哈希是 \(29\) 进制，存在哈希值无法与字母对应的情况，需要额外判断一下。
该算法时间复杂度不是很正确，因此考虑优化。对于每新增 \(6\) 位，找到合法解的概率都是 $ (\frac{26}{29})^{6} \approx 51.93%$ ，因此只枚举 \(6\) 位的成功概率就极大了。

AC代码

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int mod = 5999993;

inline int gethas(string s) {
    int ret = 0;
    for (int i = 0; i < s.length(); i++) {
        char ch = s[i];
        ret = (ret * 29 + (ch - 'a' + 1)) % mod;
    }
    return ret;
}

inline void unhas(int x) {
    char ors[1003];
    int cnt = 0;
    while (x > 0) {
        ors[cnt++] = (char)(x % 29 + 'a' - 1);
        x /= 29;
    }
    for (int i = cnt - 1; i >= 0; i--) {
        cout << ors[i];
    }
}

inline bool check(int x) {
    int cnt = 0;
    while (x > 0) {
        char ch = x % 29 + 'a' - 1;
        if (ch < 'a' || ch > 'z') return false;
        cnt++;
        x /= 29;
    }
    return cnt == 6;
}

int qpow(int a, int b) {
    a %= mod;
    int ans = 1;
    for (; b; b >>= 1, (a *= a) %= mod)
        if(b & 1) (ans *= a) %= mod;
    return ans;
}

signed main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        int A = gethas(s);
        bool flag = false;
        int B = A;
        while(true) {
            B = (B * (int) qpow(29, 6)) % mod;
            for (int i = 0; i <= 100; i++) {
                int B1 = A + mod * i - B;
                if (check(B1)) {
                    cout << s;
                    unhas(B1);
                    cout << '\n';
                    flag = true;
                    break;
                }
            }
            if (flag) break;
        }
    }
    return 0;
}