题目大意
给定一个长度不超过 $14$ 的字符串，以及素数 $m$ 和正整数 $p (p > 1)$。要求构造一个长度不超过 $14$ 的字符串，它不等于原字符串，并且以 $p$ 为进制，$m$ 为模数的哈希值等于原串的哈希值。
字符集大小为 $63$，$m \le 10^{12}, p \le 2000, p^{13} > m$。
思路分析
考虑 BSGS 算法。
我们先随机 $k$ 个长度为 $7$ 的串，将哈希值存进 std::unordered_map 中。再随机多个长度为 $7$ 的串，每次将这个串放在答案串的前半段中，再在 map 中查询后半段是否有串可以拼上去，满足整个串的哈希值为目标哈希值。找到后输出答案并退出即可。
我们将一个串的哈希值看作是 $[0, m)$ 中的随机数。不难发现期望只需要随机 $\frac{m}{k}$ 次。故 $k$ 取 $\sqrt{m}$ 最优，时间复杂度 $O(\sqrt m)$。
代码实现
1 | |
2 | |
3 | |
4 | |
5 | using namespace std; |
6 | |
7 | typedef long long ll; |
8 | const int maxn = 14, maxm = 1e6; |
9 | int n, p, k; |
10 | char s[maxn + 3], ch[100], t[10]; |
11 | ll m, goal; |
12 | unordered_map<ll, int> mp; |
13 | |
14 | struct string7 { |
15 | char s[7]; |
16 | ll h; |
17 | } s7[maxm + 3]; |
18 | |
19 | void prework() { |
20 | srand(19260817); |
21 | for (int i = 0; i < 26; i++) { |
22 | ch[k++] = 'a' + i; |
23 | } |
24 | for (int i = 0; i < 26; i++) { |
25 | ch[k++] = 'A' + i; |
26 | } |
27 | for (int i = 0; i < 10; i++) { |
28 | ch[k++] = '0' + i; |
29 | } |
30 | ch[k++] = '_'; |
31 | for (int i = 0; i < maxm; i++) { |
32 | ll &x = s7[i].h; |
33 | for (int j = 0; j < 7; j++) { |
34 | s7[i].s[j] = ch[rand() % k]; |
35 | x = (x * p + s7[i].s[j]) % m; |
36 | } |
37 | mp[x] = i; |
38 | } |
39 | } |
40 | |
41 | int main() { |
42 | scanf("%s %lld %d", s, &m, &p); |
43 | n = strlen(s); |
44 | for (int i = 0; i < n; i++) { |
45 | goal = (goal * p + s[i]) % m; |
46 | } |
47 | prework(); |
48 | ll p7 = 1; |
49 | for (int i = 0; i < 7; i++) { |
50 | p7 = p7 * p % m; |
51 | } |
52 | while (true) { |
53 | ll x = 0; |
54 | for (int i = 0; i < 7; i++) { |
55 | t[i] = ch[rand() % k]; |
56 | x = (x * p + t[i]) % m; |
57 | } |
58 | x = (__int128) x * p7 % m; |
59 | ll d = goal - x; |
60 | d < 0 ? d += m : 0; |
61 | if (mp.count(d)) { |
62 | int id = mp[d]; |
63 | printf("%s", t); |
64 | puts(s7[id].s); |
65 | break; |
66 | } |
67 | } |
68 | return 0; |
69 | } |