字典序hash大家应该都知道吧……
\[hash[i]=hash[i-1]*seed+value[i]\]
溢出不用管，相当于对2^32或2^64取模……
然后就可以O(1)取出一个子串的hash值，然后O(1)比较两个字串是否相等……
这个方法看似很靠谱
但POI的数据告诉我们，这个方法不靠谱（fotile跟我讲的，orz）
首先seed是偶数的话
显然如果两个串，低位的字符都相同，然后高位有一个字符不相同，那么hash值就会相差seed^x，这个x是个比较大的数，而seed是偶数，导致这个差值是2^32的倍数，于是就导致得出两个串hash值相同
然后seed是奇数的话
我们考虑一个01串
我们定义\(not(s)\)为字符串\(s\)的每个位置取反（0变成1，1变成0）得到的新串
我们这样构造
\[S(1)=``0"\]
\[S(n)=S(n-1)+not(S(n-1))\]
于是考虑\(S(n)\)与\(not(S(n))\)的hash值的差
可以发现
\[f( 1 ) = -1\]
\[f( n ) = f( n - 1) * ( seed ^ { 2 ^ { n - 1 } } - 1 )\]
于是
\[f( n ) = \prod_{i=0}^{n-1}(seed^{2^i}-1)\]
我们考虑\(g(k)=seed^{2^k}-1\)有多少个因数2.
显然应用平方差得
\[g(k)=seed^{2^k}-1=(seed^{2^{k-1}}-1)*(seed^{2^{k-1}}+1)=g(k-1)*(seed^{2^{k-1}}+1)\]
\(g(0)=seed-1\)，因为seed为奇数，所以至少有一个因数2
所以\(g(k)\)至少有\(k+1\)个因数2
\[f(n)=g(0)*g(1)*\cdots*g(n-1)\]
所以\(f(n)\)至少有\(1+2+3+…+n=n(n+1)/2\)个因数2
当\(n=11\)时，字符串的长度仅仅为2048，但可以保证这两个串的hash值的差至少含有66个因数2，因为对2^64取模，所以这两个串的hash值差必然为0
但事实上，这两个串没有一个字符是相同的= =
于是就被卡掉了
然后如果取多个seed，有奇有偶，也很简单，在\(S(11)\)和\(not(S(11))\)的前面和后面都各加一串相同的字符即可。这样不管seed奇数偶数都能卡掉，而且就算取100个不同的seed，每次当100个hash值全一样时候才认为两个字符串相等，也一样卡掉，因为这个方法是和seed值无关的
还有一个可能的对策是当hash值相同时，在两个串中随便找XX个位置，暴力比较是否相同…… 这个我们也可以卡，只要把“在前面和后面加的一串相同的字符”的长度搞大一点，一般这种题目字符串规模都是10W，我10万个字符里就2048个字符不同，其他字符全都相同，你每次暴力取20个字符能保证正好摸到我2048个字符里面？ 而且这种题目一般还是反复询问，那我就反复查询这10W个字符是否相同，你这次摸到了，下次还能摸到？ 下次又摸到了我还不信你10W个询问都能摸到…… 一次摸不到你就挂了…… 所以这种方法也没用……
目前我想到的解决方法是：
不用字典序hash
或者不要用自然溢出，还是对一个大质数取模靠谱一点，虽然这样速度会慢一点……