关于字符串哈希的疑惑
  • 板块学术版
  • 楼主olegekei
  • 当前回复18
  • 已保存回复18
  • 发布时间2022/11/5 17:10
  • 上次更新2023/10/27 04:11:14
查看原帖
关于字符串哈希的疑惑
593613
olegekei楼主2022/11/5 17:10

一般我们可以把字符串哈希看成一个 base\text{base} 进制的数,有的哈希会对一个大质数 mod\text{mod} 进行取模,不取模则是自然溢出,一般会开 unsigned\text{unsigned}

一般 base\text{base} 的值根据题目内的字符数量决定,比如P3370【模板】字符串哈希,题目里包含大小写字母和数字,那么可以取 base=26+26+10=62\text{base}=26+26+10=62,也可以取更大一点。

然后疑惑产生了:

这道题我取 base=2\text{base}=2,能过这道题。

除了此题之外还有一道关于哈希的紫题P3538 OKR-A Horrible Poem ,同学写这道题的时候设 base=26\text{base}=26 的时候错六个点,又设 base=27\text{base}=27 才过。而我用同一份代码设 base=5\text{base}=5 反而过了。

但是我个人理解 2626 个字母的话 base\text{base}55 应该更容易错,反而相较于 base=26\text{base}=26 AC 了。

所以字符串哈希的取 base\text{base} 的值的时候有什么要求吗,或者怎样取 base\text{base} 的值能够提高正确率?

2022/11/5 17:10
加载中...