poj 1200 Crazy Search (字符串哈希)

题目链接

题意:一个字符串,其仅由nc种字符组成,问其所有长度为n的字串里,共用多少种不同的。

思路:一开始木有懂nc种字符有什么用…

然后写了hash,发现会TLE。。。因为用到了map,被卡了个log..

nc的作用是,可以把字符串看成一个nc进制的数,这样做的好处是,得到的hash值可以尽可能的小而且保证了不同的字符串对应了不同的hash值。

然后就可以不用map而是一个数组,就变成了O(1)赋值和判断了。。。

(然而没有数据范围其实还是有点耍流氓的嫌疑。。

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz