拉链法
字符串前缀hash
( s="ABCDDDC"\ P=131 (or) 13331,M=2^(64)\ c++中unsigned int 溢出相当于自动对2^(64)取模\ h[0]=0;\ h[1]="A"的hash值\ h[2]="AB"的hash值\ h[3]="ABC"的hash值\ s="ABCD"\ =(1,2,3,4)p进制\ =(1*p^3+2*p^2+3*p+4)mod M;\ 注意一般字母不能映射成0，否则若a=0,aa=0,aaa=0,无法区分\ 已知h[r],h[l-1];\ [1.........l......r];\ \ 应用求[l~r]的hash值\ 左边为高位，右边为低位\ r-1...............0 h[r]\ l-2...l-1.l h[l-1]\ h[r]与h[l-1]相差r-1-(l-2)==r-l+1位\ h[r]-h[l-1]*p^(r-l+1)==hash[l~r]\ )