卡哈希

cancan123456 · 2024-02-24 18:35:01 · 算法·理论

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

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

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

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

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

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

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

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

单模哈希

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

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

自然溢出哈希

题解：

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

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

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

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

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

aaaaaaadaaaacacacacacbaadbcaccbaacecaaacadebabaaaa
aabbbaaabfbaaeabacadaaacaaafaaadbaaaaaeafaaabaaaaa

所以构造这组数据：

1
100 1
aaaaaaadaaaacacacacacbaadbcaccbaacecaaacadebabaaaaaaaaabaaafaeaaaaabdaaafaaacaaadacabaeaabfbaaabbbaa
1 100

即可叉掉此提交！

参考代码：

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 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}。

那么我们有：

参考代码：

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]))