BISHI7　字符串哈希¶

简单通过率 78.6%python3样例通过牛客 AC

一句话

求 N 个字符串里有多少个不同的。

解题思路¶

这题考什么¶

题目名叫「字符串哈希」，C++ 里的标准做法是给每个串算一个多项式哈希（或双哈希）再去重，避免 O(N^2 * |s|) 的两两比较。 Python 里 str/bytes 本身就是可哈希的，set 内部就是哈希表，而且哈希计算是 C 实现的 SipHash，比手写多项式哈希又快又不会被卡冲突—— 所以直接 len(set(...)) 就是本题的正解，不需要自己造轮子。

数据规模与复杂度¶

N <= 1e4，|s| <= 1500，总字符量最多 1.5e7，一次性读入约 15MB，空间限制 512MB 完全放得下。建 set 的复杂度 O(总字符量)（每个串哈希一次 + 冲突时比较一次），比两两比较的 O(N^2 |s|) = 1.5e11 快了 4 个数量级。

坑在哪¶

区分大小写，不能 lower()：样例里 Hello / hello / HELLO 算 3 个不同串；
串里只有数字和大小写字母（无空格），所以可以放心用 split() 按空白切 token，不必逐行 readline；
只取前 N 个 token，防止输入尾部有多余空行/脏数据；
直接对 bytes 去重，省掉 1e4 次 decode——两个 bytes 相等当且仅当字节序列相同，与 decode 成 str 再比较等价，这里没有编码歧义（输入只有数字和大小写字母）；
「不同字符串的个数」是去重后的数量，不是「只出现一次的字符串个数」，样例里 Hello 出现两次仍然只算一个。

样例复核¶

6 个串里 Hello 重复一次，去重后剩 Hello、World、hello、HELLO、Code 共 5 个，与样例一致；若误用 lower() 去重则只剩 3 个。

前置章节¶

08-集合、36-哈希与字符串哈希

参考实现¶

solutions/BISHI7.py
import sys


def main() -> None:
    # 串里只有数字和字母、不含空白，所以按空白切 token 后每个元素恰好是一个串
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    # data[0] 是 N 本身，串从下标 1 开始；只取前 n 个，避免尾部空行等脏数据混入。
    # set 去重靠内置哈希（C 实现），比手写多项式哈希更快，也不会被出题人卡冲突
    sys.stdout.write(str(len(set(data[1:1 + n]))) + "\n")


main()

BISHI7 字符串哈希¶