当前位置:首页 > 离散化 > 哈希表 > 正文
洛谷P3370【模板】字符串哈希
8397+

题目大意:给定N个字符串(第i个字符串长度为Mi,字符串内包含数字、大小写字母,大小写敏感),请求出N个字符串中共有多少个不同的字符串。

输入输出格式

输入格式:

第一行包含一个整数N,为字符串的个数。

接下来N行每行包含一个字符串,为所提供的字符串。

输出格式:

输出包含一行,包含一个整数,为不同的字符串个数。

输入输出样例

输入样例#1:

5
abc
aaaa
abc
abcc
12345

输出样例#1:

4

说明

时空限制:1000ms,128M

数据规模:

对于30%的数据:N<=10,Mi≈6,Mmax<=15;

对于70%的数据:N<=1000,Mi≈100,Mmax<=150

对于100%的数据:N<=10000,Mi≈1000,Mmax<=1500

样例说明:

样例中第一个字符串(abc)和第三个字符串(abc)是一样的,所以所提供字符串的集合为{aaaa,abc,abcc,12345},故共计4个不同的字符串。

解题思路

字符串有10000个,每个长1000,逐个查询太慢,可以使用哈希表。

哈希表中,可以记录这个字符串及其长度。如果找到则重复,否则是新字符串。我们既可以统计重复个数,也可以统计新字符串个数,都是一样的。

至于哈希函数,写法很多种。如每个字符串的哈希值的求法,就有非常多的方法。如字符串中每一个字符的ASCII码直接加起来或者乘起来,又或者第一个字符*长度,第二个字符*1,第三个字符*2……当然,不一定每个字符都要用到,你也要只用奇数位或者偶数位,又或者3的倍数、5的倍数、7的倍数……本程序(第10行)用的是末尾字符和字符串长度做哈希,因为字符串长度比较大。当然你要加上首字符也可以。

程序实现

About

坚决不Copy代码!

本文标签:,,,,

洛谷P3370【模板】字符串哈希:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!