P3370 【模板】字符串哈希
题目描述
如题,给定 NNN 个字符串(第 iii 个字符串长度为 MiM_iMi ,字符串内包含数字、大小写字母,大小写敏感),请求出 NNN 个字符串中共有多少个不同的字符串。
友情提醒:如果真的想好好练习哈希的话,请自觉。
输入格式
第一行包含一个整数 NNN,为字符串的个数。
接下来 NNN 行每行包含一个字符串,为所提供的字符串。
输出格式
输出包含一行,包含一个整数,为不同的字符串个数。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
数据范围
对于 30%30\%30% 的数据:N≤10N\leq 10N≤10,Mi≈6M_i≈6Mi ≈6,Mmax≤15M_{\max}\leq 15Mmax ≤15。
对于 70%70\%70% 的数据:N≤1000N\leq 1000N≤1000,Mi≈100M_i≈100Mi ≈100,Mmax≤150M_{\max}\leq 150Mmax ≤150。
对于 100%100\%100% 的数据:N≤10000N\leq 10000N≤10000,Mi≈1000M_i≈1000Mi ≈1000,Mmax≤1500M_{\max}\leq 1500Mmax ≤1500。
样例说明
样例中第一个字符串 abc\tt{abc}abc 和第三个字符串 abc\tt{abc}abc 是一样的,所以所提供字符串的集合为 {aaaa,abc,abcc,12345}\{\tt{aaaa},\tt{abc},\tt{abcc},\tt{12345}\}{aaaa,abc,abcc,12345},故共计 444 个不同的字符串。
拓展阅读
以下的一些试题从不同层面体现出了字符串哈希算法的正确性分析。
* P12197 Hash Killer I
* P12198 Hash Killer II
* P12199 (目前无解)Hash Killer III
* P12200 Hash Killer Extra
* P12201 Hash Killer Phantasm
* P7350 「MCOI-04」Dream and Strings