字符串哈希主要用于判断两个字符串是否相等，可以做到O(n)预处理，O(1)查询。

其实就是把字符串看成一个数字，其进制为base（应大于字符种类），另外还要对某个数取模，可以自己选择一个大质数，也可以让其对unsigned int或unsigned long long自然溢出。

因为是取过模，所以可能发生哈希冲突，一般让其自然溢出更容易被故意卡掉；选择两个大质数，利用两个哈希值来判断据说不会被卡，但常数较大。

1 typedef unsigned long long ull; 2 const ull base=233; 3 int hs[maxn],pw[maxn]; 4 char s[maxn]; 5 void init() { //预处理出基数的n次幂及前缀哈希 6     pw[0]=1; 7     for(int i=1;i<=n;++i) pw[i]=pw[i-1]*base; 8     hs[0]=s[0]; 9     for(int i=1;i

这里我们采用了前缀的思想，而求某一子串的哈希值，就是将其左端点的上一个点的前缀推进，用右端点的前缀相减就是子串的哈希，最好手动模拟一下。

字符串哈希还有一种应用，可以在O(log)的时间复杂度下判断子串的大小，二分两个子串，求出他们最长公共前缀，具体实现我是求第一次不同的位置，若这个位置超出了子串范围，说明他们相等，否则比较这个位置上的字符大小即可。

1         int l1,r1,l2,r2; 2     scanf("%d%d%d%d",&l1,&r1,&l2,&r2); 3     int i=l1,j=r1,k=l2+1,l=l2+1; //注意这里的下标，我们要找的是第一个不一样的位置 4     while(i
     
      
       r1&&k>r2) printf("=");10     else if(r1-l1>r2-l2||s[l1]>s[l2]) printf(">");11     else printf("<");