题解 | 哈希冲突

import hashlib
import string
import random
def sha256(text: str) -> str:
    return hashlib.sha256(text.encode()).hexdigest()

enc_len = 0
enc_key = ""

def H(s):
    combined = enc_key + s
    return sha256(combined)[:enc_len]

def solve():
    # 在此处补全代码
    seen_hashes = {}#用于存储key:H(s)（字符串的哈希值）,val:s（字符串）
    chars = "abcdefghijklmnopqrstuvwxyz"#存储所有小写字母，用于随机生成字符串
    #生日攻击算法，随着我们测试的输入数量增加，新的输出与所有旧的输出发生碰撞的概率会迅速增长。
    while True:
        s = "".join(random.choice(chars) for _ in range(enc_len))#随机生成字符串
        h = H(s)#计算s的哈希值
        if h in seen_hashes:
            s1=seen_hashes[h]#取出存在哈希表中的s1
            if s1!=s:
                return (s1,s)if s1<s else (s,s1)#返回字典序较小的在前
        else:
            seen_hashes[h]=s




































































































































































































































































def main():
    global enc_len, enc_key
    enc_len = int(input())
    enc_key = input()
    
    result = solve()
    print(f"{result[0]} {result[1]}")

if __name__ == "__main__":
    main()