本文摘自 cancan123456 的《卡哈希》。

本文基于 NOI WC 2024 csy 专家进行的讲解。

什么？你还在为卡不掉选手的十模哈希而感到痛苦？

什么？你还在 CF hack 时看着对方的随机五十模数哈希而感到迷茫？

不要担心，现隆重向您推出——LLL 算法卡哈希！

在这之前，我们快速回顾一下几种简单的卡哈希方法。

OI 中常见的字符串哈希函数一般形如下式：

其中 $0\le s_i<26\le b<p$，且 $p$ 一般为质数。

多模哈希是选择多组 $(b,p)$，将 $H(s)$ 构成的有序对作为哈希结果。

单模哈希

相信这个东西的卡法已经为人熟知了，直接随机一堆字符串看看有没有相同即可，利用了生日悖论。

这个做法挂亿会机也能找到双模哈希的碰撞。

自然溢出哈希

$p=2^{64}$，对 $b$ 的奇偶性分类讨论：

  1. $b$ 为偶数，那么有

所以只需要构造低 $64$ 位相同的字符串即可。

  1. $b$ 为奇数，我们考虑字符集为 $\{0,1\}$ 的字符串 $s$，定义其取反 $\bar s$ 为 $0$ 变为 $1$，$1$ 变为 $0$ 后得到的字符串。令 $s_1=[0],s_{i+1}=s_i+\bar{s_i}$，那么容易发现 $H(s_{12})=H_{\bar{s_{12}}}$。

多模哈希

众所周知，某些选手在不会写 SA 或者 Z-function 或者 Manacher 等等字符串算法时会选择二分哈希这种做法，对于写正解的选手非常不公平，在介绍如何针对这些选手之前，先对 Lenstra-Lenstra-Lovász Lattice Reduction 算法 进行介绍。

格与基

本文只关注欧几里得空间中由向量加法构成的格，所以我们给出格的定义：

格 是欧几里得空间 $\mathbb R^n$ 的一个离散加法子群，且其中的元素可由 $n$ 个整系数的向量 基 线性组合生成。

换句话说，基就是 $n$ 个整数向量 $\vec{v_i}$，格就是所有的 $\sum k_i\vec{v_i},k_i\in\mathbb Z$。

Gram-Schmidt 正交化

先定义正交基：

正交基 是一组基 $\vec{v_i}$，满足：

Gram-Schmidt 正交化可以将一组基 $\vec{v_i}$ 变为一组正交基 $\vec{v_i}^\ast$。

Gram-Schmidt 正交化采用增量法构造，加入第一个向量时，直接令 $\vec{v_1}^\ast=\vec{v_1}$ 即可。

加入第 $n+1$ 个向量时，我们考虑计算 $\vec{v_n}$ 对 $\vec{v_i}^\ast,1\le i<n$ 的投影，从 $\vec{v_n}$ 中减去投影，具体可以参考这个图：

然后我们就得到了这个公式：

LLL 算法主体

LLL 算法有一个参数 $\delta$，需要满足 $\dfrac14<\delta<1$，一般取 $\delta=\dfrac34$。

定义一组基 $\vec{v_i}$ 的 LLL reduced 条件：

$\textbf{Lov’asz Condition}$ 的一个等价表述为：

其中 $\vec{v_i}^\ast$ 为 $\vec{v_i}$ 的 Gram-Schmidt 正交化基，还是增量法，对于 $n=1$，我们什么也不用做就可以满足两个条件。

现在假设我们已经把 $\vec{v_i},1\le i<k$ 变换成了 LLL reduced 的，我们加入了新向量 $\vec{v_k}$，我们先求出这些向量的 Gram-Schmidt 正交化基 $\vec{v_i}^\ast$，为了满足 $\textbf{Size Condition}$，我们枚举 $j$ 从 $k-1$ 到 $1$，执行：

（$\lfloor x\rceil$ 表示 $x$ 四舍五入。）检查一下 $\textbf{Lov’asz Condition}$ 是否成立，如果成立，我们直接令 $k\gets k+1$，否则，我们交换 $\vec{v_{k-1}}$ 与 $\vec{v_k}$，并令 $k\gets\max(k-1,2)$，与更前面的基进行比较。

这个算法的正确性证明和终止性证明和时间复杂度证明都比较复杂，所以就不写了（就是不会）。

LLL reduced 基有如下性质：

设 $\vec{v_i}$ 是 $n$ 维格 $\mathcal L$ 的一组 LLL reduced 基，那么有：

其中 $\lambda_1(\mathcal L)$ 为格 $\mathcal L$ 中的最短向量长度，求解该向量被称为 SVP 问题（Shortest Vector Problem）。

证明可以归纳法，所以我们直接把 $\delta$ 拉满（比如 $0.99$）就能产生一组不错的基，这个算法的时间复杂度是 $O(n^6\log^3B)$，其中 $B$ 是 $\max|\vec{v_i}|$，当然实际运用中严重跑不满。

这样 LLL 算法就找到了 SVP 问题的一个近似解。

CVP

格中的困难问题之一——Closest Vector Problem，寻找格 $\mathcal L$ 中与向量 $\vec t$ 最近的向量（虽然这和怎么卡哈希没有关系，还是讲一下吧）。

Babai’s nearest plane algorithm：首先将 $\mathcal L$ 跑一遍 LLL 得到 LLL reduced 基 $\vec{v_i}$，置 $\vec b=\vec t$，枚举 $j$ 从 $n$ 到 $1$，令 $\vec b=\vec b-\left\lceil\dfrac{\vec b\cdot\vec{b_j}}{\vec{b_j}\cdot\vec{b_j}}\right\rceil\vec{v_j}$，最后的 $\vec b$ 就是一个比较好的解。

近似程度有多好呢？我们有这个算法求出的解至多是正确答案的 $2^{n/2}$ 倍。

对 LLL 卡常

下面是 sagemath 中 LLL 算法的实现，假设我们需要对由 $\vec{y_i}$ 生成的格进行 LLL 算法。

首先计算 Gram-Schmidt 正交化基 $\vec{y_i}^\ast$ 和 $\mu$ 矩阵，计算 $\gamma_i=|\vec{x_i}|^2$，令 $k=2$ 表示我们准备好添加 $\vec{y_k}$ 进入 LLL reduced 基了。

首先定义 reduce(k, l) 过程：如果 $|\mu_{k,l}|>\dfrac12$，令 $\vec{y_k}\gets\vec{y_k}-\lfloor\mu_{k,l}\rceil\vec{y_l}$，然后对于所有 $1\le j<l$，将 $\mu_{k,j}$ 减去 $\lfloor\mu_{k,l}\rceil\mu_{l,j}$。

最后令 $\mu_{k,l}\gets\mu_{k,l}-\lfloor\mu_{k,l}\rceil$ 即可。

然后定义 exchange(k) 过程：交换 $\vec{v_k},\vec{v_{k-1}}$，令 $\nu=\mu_{k,k-1},\delta=\gamma_k+\nu^2\gamma_{k-1}$ 更新 $\mu_{k,k-1}=\dfrac{\nu\gamma_{k-1}}\delta,\gamma_k=\dfrac{\gamma_k\gamma_{k-1}}\delta,\gamma_{k-1}=\delta$。

然后对于所有 $1\le j<k-1$，交换 $\mu_{k-1,j},\mu_{k,j}$，对于所有 $k+1\le j\le n$，令 $x_i=\mu_{i,k}$，并置 $\mu_{i,k}=\mu_{i,k-1}-\nu\mu_{i,k},\mu_{i,k-1}=\mu_{k,k-1}\mu_{i,k}+x_i$。

等会补充证明。

然后令 $k=2$，重复执行直到 $k>n$：

  1. reduce(k, k - 1)
  2. 如果 $\gamma_k\ge(\delta-\mu_{k,k-1}^2)\gamma_{k-1}$，倒序枚举 $l=k-1\to 1$，reduce(k, l)，将 $k$ 加 $1$。
  3. 否则，exchange(k) 并令 $k=\max(k-1,2)$。

卡掉哈希！

考虑将构造哈希碰撞转换为求解一个格的 SVP 问题。

首先看这个题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
h0 = 45740974929179720441799381904411404011270459520712533273451053262137196814399

# 2**168 + 355
g = 374144419156711147060143317175368453031918731002211L


def shitty_hash(msg):
    h = h0
    msg = map(ord, msg)
    for i in msg:
        h = (h + i) * g
        # This line is just to screw you up :))
        h = h & 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

    return h - 0xe6168647f636

也就是 $b=2^{168}+355,p=2^{256}$ 的 $H$，你需要构造两个串满足其哈希相同。

不妨设我们构造的两个串为 $s_i,t_i$，那么有：

容易将问题转化为构造长 $n$ 的整数序列 $x_i=s_i-t_i$ 和整数 $k$，满足 $\sum x_ib^{n-i}-kp=0$，考虑构造这样的格：

其中 $K$ 是一个大常数，比如 $2^{200}$，然后跑 LLL 算法，求一个 SVP。

注意到我们的 $K$ 非常大，所以求出的 SVP 如果在 $K$ 这个维度不是 $0$，那么一定非常长，所以这个维度一定是 $0$，就满足了条件。

由于我不想下 sagemath，于是就有了下面的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
from sympy import *

mod = 2 ** 256
h0 = 45740974929179720441799381904411404011270459520712533273451053262137196814399
g = 374144419156711147060143317175368453031918731002211
K = 2 ** 200
N = 50
y = []
for i in range(N):
    y.append([])
    for j in range(N + 1):
        if i == j:
            y[i].append(Rational(1, 1))
        elif j == N:
            y[i].append(Rational(K * pow(g, N - i, mod), 1))
        else:
            y[i].append(Rational(0, 1))
def dot(x, y):
    n = len(x)
    ans = 0
    for i in range(n):
        ans += x[i] * y[i]
    return ans
delta = Rational(99, 100)
n, m = N, N + 1
y_star = [[y[0][i] for i in range(m)]]
mu = [[Rational(0, 1) for i in range(m)] for j in range(n)]
for i in range(1, n):
    print('Gram-Schmidt: i =', i)
    y_star.append([y[i][j] for j in range(m)])
    for j in range(i):
        mu[i][j] = dot(y_star[j], y_star[i]) / dot(y_star[j], y_star[j])
        for k in range(m):
            y_star[i][k] -= y_star[j][k] * mu[i][j]
gamma = [dot(y_star[i], y_star[i]) for i in range(n)]
def round(x):
    return (x + Rational(1, 2)).floor()
def reduce(k, l):
    if abs(mu[k][l]) > Rational(1, 2):
        for i in range(m):
            y[k][i] -= round(mu[k][l]) * y[l][i]
        for j in range(l):
            mu[k][j] -= round(mu[k][l]) * mu[l][j]
        mu[k][l] -= round(mu[k][l])
def exchange(k):
    y[k - 1], y[k] = y[k], y[k - 1]
    nu = mu[k][k - 1]
    delta = gamma[k] + nu * nu * gamma[k - 1]
    mu[k][k - 1] = nu * gamma[k - 1] / delta
    gamma[k] *= gamma[k - 1] / delta
    gamma[k - 1] = delta
    for j in range(k - 1):
        mu[k - 1][j], mu[k][j] = mu[k][j], mu[k - 1][j]
    for i in range(k + 1, n):
        xi = mu[i][k]
        mu[i][k] = mu[i][k - 1] - nu * mu[i][k]
        mu[i][k - 1] = mu[k][k - 1] * mu[i][k] + xi
k = 1
maxk = 1
while k < n:
    if maxk < k:
        maxk = k
        print('LLL: new k =', k)
    reduce(k, k - 1)
    if gamma[k] >= (delta - mu[k][k - 1] ** 2) * gamma[k - 1]:
        for l in range(k - 2, -1, -1):
            reduce(k, l)
        k = k + 1
    else:
        exchange(k)
        if k > 1:
            k = k - 1
def shitty_hash(msg):
    h = h0
    msg = map(ord, msg)
    for i in msg:
        h = (h + i) * g
        # This line is just to screw you up :))
        h = h & 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

    return h - 0xe6168647f636
s1 = 'a' * n
s2 = ''
for i in range(n):
    s2 += chr(ord(s1[i]) + y[0][i])
print(y[0])
print(max(y[0]), min(y[0]), max(y[0]) - min(y[0]))
print(s1)
print(s2)
print(shitty_hash(s1))
print(shitty_hash(s2))
if shitty_hash(s1) == shitty_hash(s2):
    print('ok')
else:
    print('wa')

在一万两千多次迭代之后，LLL 算法给出的如下的 $\vec{y_0}$：

并产生了两个串：

1
2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
pSrogamvi~g]Xk_U[aUnEEI^g\QprSd_QHdLFXqf`a^]]Ngiaa

并其 hash 值都是

Tree Attack

来源：On the mathematics behind rolling hashes and anti-hash tests。

有的时候，选手会对每个字符给定一个随机权值的方法来防止自己的哈希被 LLL 卡掉，这是非常不好的。

Tree Attack 尝试找到 $\alpha_i\in\{-1,0,1\}$ 满足：

中的 $s_i-t_i$ 将被限制于 $\{-1,0,1\}$ 中，定义一个簇 $C$ 是 $\{0,1,\dots,n-1\}$ 的子集，定义簇的和为：

我们维护系数 $\alpha_i$ 上的簇 $C_1,C_2,\dots$。

我们可以将两个簇 $C_1,C_2$ 合并为一个满足 $S(C_3)=|S(C_1)-S(C_2)|$ 的簇 $C_3$：不妨设 $S(C_1)>S(C_2)$，我们将 $C_2$ 中的 $\alpha_i$ 全部取反然后令 $C_3=C_1\cup C_2$ 即可。

初始令 $n=2^k$（$k$ 在下面会进行分析），我们令 $\alpha_i=1$，并创建 $n$ 个簇 $C_i$，其中仅包含 $\{i\}$。

在每一轮中，我们对所有簇 $C$ 按照 $S(C)$ 排序，然后合并相邻的簇，如果我们得到了一个 $S(C)=0$ 的簇 $C$，将不在 $C$ 中的所有 $\alpha_i$ 全部置为 $0$，并返回这些 $\alpha_i$。

$k$ 的值应该取多少？我们可以合理地假设 $b^{n-i-1}\bmod p$ 在 $[0,p)$ 中均匀分布，那么在 $i$ 轮之后，最大值应当除以大约 $2^i$，所以 $k$ 轮以后，最大值大约为 $\dfrac p{2^{k(k-1)/2}}$，所以 $k\approx\sqrt{2\log p}+1$ 是一个合理的选择。

Multi Tree Attack

在 Tree Attack 的基础上，将每个簇能得到的最小的 $m$ 个值存储，显然可以在 $O(m\log m)$ 时间内合并两个簇。

实战演练

叉掉 CF Submission 251754156，来自 $\color{purple}\sf \text{a_little_cute}$ 在 CF Round 934 (Div. 1) 对 B 题的提交。

题意简述：

定义字符串 $t$ 是 $k$-好的当且仅当存在一个非回文的长 $k$ 的 $t$ 的子串。

对于字符串 $t$ 定义 $f(t)$ 为所有满足 $t$ 是 $k$-好的正整数 $k$ 之和。

给定长 $n$ 字符串 $s$ 与 $q$ 次询问 $l,r$，求 $f(s_{l\sim r})$ 的值。

$1\le n,q\le10^5$

题解：

如果串里全部都相同，那么答案为 $0$。如果所有奇数位置的字符和偶数位置的字符都相同，那么 $k$ 只能是偶数。

注意特判一下整个串是否是回文串即可。

重点来了，我们需要快速判断一个子串 $s_{l\sim r}$ 是回文的。

这位选手采用了四模哈希与固定底数 $31$，模数列表为 $995662561,995662609,995662621,998244353$。

用上面的模板可以找到如下碰撞：

1
2
aaaaaaadaaaacacacacacbaadbcaccbaacecaaacadebabaaaa
aabbbaaabfbaaeabacadaaacaaafaaadbaaaaaeafaaabaaaaa

所以构造这组数据：

1
2
3
4
1
100 1
aaaaaaadaaaacacacacacbaadbcaccbaacecaaacadebabaaaaaaaaabaaafaeaaaaabdaaafaaacaaadacabaeaabfbaaabbbaa
1 100

即可叉掉此提交！

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import fractions as f
K = 2 ** 50
N = 50
cnt = 4
mod_ = [995662561, 995662609, 995662621, 998244353]
base_ = [31, 31, 31, 31]
y = []
for i in range(N):
    y.append([])
    for j in range(N):
        if i == j:
            y[i].append(f.Fraction(1, 1))
        else:
            y[i].append(f.Fraction(0, 1))
    for j in range(cnt):
        y[i].append(f.Fraction(pow(base_[j], N - i, mod_[j]) * K, 1))
def dot(x, y):
    n = len(x)
    ans = 0
    for i in range(n):
        ans += x[i] * y[i]
    return ans
delta = f.Fraction(99, 100)
n, m = N, N + cnt
y_star = [[y[0][i] for i in range(m)]]
mu = [[f.Fraction(0, 1) for i in range(m)] for j in range(n)]
for i in range(1, n):
    print('Gram-Schmidt: i =', i)
    y_star.append([y[i][j] for j in range(m)])
    for j in range(i):
        mu[i][j] = dot(y_star[j], y_star[i]) / dot(y_star[j], y_star[j])
        for k in range(m):
            y_star[i][k] -= y_star[j][k] * mu[i][j]
gamma = [dot(y_star[i], y_star[i]) for i in range(n)]
def round(x):
    return (x + f.Fraction(1, 2)).__floor__()
def reduce(k, l):
    if abs(mu[k][l]) > f.Fraction(1, 2):
        for i in range(m):
            y[k][i] -= round(mu[k][l]) * y[l][i]
        for j in range(l):
            mu[k][j] -= round(mu[k][l]) * mu[l][j]
        mu[k][l] -= round(mu[k][l])
def exchange(k):
    y[k - 1], y[k] = y[k], y[k - 1]
    nu = mu[k][k - 1]
    delta = gamma[k] + nu * nu * gamma[k - 1]
    mu[k][k - 1] = nu * gamma[k - 1] / delta
    gamma[k] *= gamma[k - 1] / delta
    gamma[k - 1] = delta
    for j in range(k - 1):
        mu[k - 1][j], mu[k][j] = mu[k][j], mu[k - 1][j]
    for i in range(k + 1, n):
        xi = mu[i][k]
        mu[i][k] = mu[i][k - 1] - nu * mu[i][k]
        mu[i][k - 1] = mu[k][k - 1] * mu[i][k] + xi
k = 1
maxk = 1
while k < n:
    if maxk < k:
        maxk = k
        print('LLL: new k =', k)
    reduce(k, k - 1)
    if gamma[k] >= (delta - mu[k][k - 1] ** 2) * gamma[k - 1]:
        for l in range(k - 2, -1, -1):
            reduce(k, l)
        k = k + 1
    else:
        exchange(k)
        if k > 1:
            k = k - 1
print(y[0])
s1 = s2 = ''
for i in range(n):
    now = int(y[0][i])
    if now <= 0:
        s1 += 'a'
        s2 += chr(ord('a') - now)
    else:
        s1 += chr(ord('a') + now)
        s2 += 'a'
print(s1)
print(s2)
def calc_hash(s, b, m):
    ans = 0
    for i in range(len(s)):
        ans = (ans + (ord(s[i]) - ord('a')) * pow(b, N - i, m)) % m
    return ans
for i in range(cnt):
    print(calc_hash(s1, base_[i], mod_[i]), calc_hash(s2, base_[i], mod_[i]))

构造非回文的“回文”串

叉掉 CF Submission 251715199，来自 $\color{red}\sf \text{Crystally}$ 在 CF Round 934 (Div. 1) 对 B 题的提交。

这要求我们构造一个串 $s$ 满足 $H(s)=H(r(s))$，$r(s)$ 表示 $s$ 逆序得到的字符串，不妨设 $s$ 长度为 $2n$，那么：

我们设 $x_i=s_i-s_{2n-i+1}$，则对于 $i+j=2n+1$，有 $x_i=-x_j$，所以我们只需要 $x_{1\sim n}$。

那么我们有：

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
import fractions as f
K = 2 ** 200
N = 50
cnt = 1
mod_ = [2305843009213693951]
base_ = [1145141919]
y = []
for i in range(N):
    y.append([])
    for j in range(N):
        if i == j:
            y[i].append(f.Fraction(1, 1))
        else:
            y[i].append(f.Fraction(0, 1))
    for j in range(cnt):
        #y[i].append(f.Fraction(pow(base_[j], N - i, mod_[j]) * K, 1))
        y[i].append(f.Fraction((pow(base_[j], 2 * N - i - 1, mod_[j]) - pow(base_[j], i, mod_[j])) % mod_[j] * K, 1))
def dot(x, y):
    n = len(x)
    ans = 0
    for i in range(n):
        ans += x[i] * y[i]
    return ans
delta = f.Fraction(99, 100)
n, m = N, N + cnt
y_star = [[y[0][i] for i in range(m)]]
mu = [[f.Fraction(0, 1) for i in range(m)] for j in range(n)]
for i in range(1, n):
    print('Gram-Schmidt: i =', i)
    y_star.append([y[i][j] for j in range(m)])
    for j in range(i):
        mu[i][j] = dot(y_star[j], y_star[i]) / dot(y_star[j], y_star[j])
        for k in range(m):
            y_star[i][k] -= y_star[j][k] * mu[i][j]
gamma = [dot(y_star[i], y_star[i]) for i in range(n)]
def round(x):
    return (x + f.Fraction(1, 2)).__floor__()
def reduce(k, l):
    if abs(mu[k][l]) > f.Fraction(1, 2):
        for i in range(m):
            y[k][i] -= round(mu[k][l]) * y[l][i]
        for j in range(l):
            mu[k][j] -= round(mu[k][l]) * mu[l][j]
        mu[k][l] -= round(mu[k][l])
def exchange(k):
    y[k - 1], y[k] = y[k], y[k - 1]
    nu = mu[k][k - 1]
    delta = gamma[k] + nu * nu * gamma[k - 1]
    mu[k][k - 1] = nu * gamma[k - 1] / delta
    gamma[k] *= gamma[k - 1] / delta
    gamma[k - 1] = delta
    for j in range(k - 1):
        mu[k - 1][j], mu[k][j] = mu[k][j], mu[k - 1][j]
    for i in range(k + 1, n):
        xi = mu[i][k]
        mu[i][k] = mu[i][k - 1] - nu * mu[i][k]
        mu[i][k - 1] = mu[k][k - 1] * mu[i][k] + xi
k = 1
maxk = 1
while k < n:
    if maxk < k:
        maxk = k
        print('LLL: new k =', k)
    reduce(k, k - 1)
    if gamma[k] >= (delta - mu[k][k - 1] ** 2) * gamma[k - 1]:
        for l in range(k - 2, -1, -1):
            reduce(k, l)
        k = k + 1
    else:
        exchange(k)
        if k > 1:
            k = k - 1
print(y[0])
s1 = s2 = ''
for i in range(n):
    now = int(y[0][i])
    if now <= 0:
        s1 += 'a'
        s2 += chr(ord('a') - now)
    else:
        s1 += chr(ord('a') + now)
        s2 += 'a'
print(s1)
print(s2)
print(s1 + s2[::-1])
def calc_hash(s, b, m):
    ans = 0
    for i in range(len(s)):
        ans = (ans + (ord(s[i]) - ord('a')) * pow(b, i, m)) % m
    return ans
s = s1 + s2[::-1]
#for i in range(cnt):
#    print(calc_hash(s1, base_[i], mod_[i]), calc_hash(s2, base_[i], mod_[i]))
for i in range(cnt):
    print(calc_hash(s, base_[i], mod_[i]), calc_hash(s[::-1], base_[i], mod_[i]))
License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

Share