哈希大法，用空间换时间的典例，此前已经学习过，今日写一篇博客记录一下。

自然溢出法

开一个unsigned long long，大小2^64-1，利用无负数的性质自然溢出。

Hash公式：

单哈希法

增加了Mod，代替自然溢出。自然溢出也是单哈希。

Hash公式

双哈希法

哈希大法最怕的就是冲突，因此取两组Base和Mod，将哈希结果作为二元组保存，冲突概率极低。

Hash公式

获取子串哈希值

hash[i]存的是[0,i]子串的哈希值，那么如何求任意子串的哈希值呢？

例子

公式

面对取模时一定要谨慎谨慎再谨慎。。。

Tips

OI Wiki中写了卡掉单哈希，溢出法的方法，说明单哈希的风险还是挺大的，如果题目时间允许还是写个双哈希比较安全，但在运行速度上溢出法是最快的，也是最容易卡掉的。