Java教程

【字符串】字符串多项式哈希 - 第2节

本文主要是介绍【字符串】字符串多项式哈希 - 第2节，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

昨天看群里讨论哈希使用自然溢出被卡的问题，突然想到一个问题，就是为什么需要使用双模去做字符串哈希才能有效保证正确率呢？

把n个元素放进m个桶里面，不发生冲突的概率：

\[P = e^{\frac{-n(n-1)}{2m}) \]

求解这个式子可以得知，要求正确率达到1e-9级别的话，m大概需要n的平方的量级。但是经常发现1e9的取模会被卡，应该是有办法故意构造一些字符串让他冲突。

https://codeforces.com/blog/entry/60442

这里面讲述了为什么字符串哈希要选取质数作为模。

这篇关于【字符串】字符串多项式哈希 - 第2节的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航