Hash

Hash表也叫散列表，可以将复杂而庞大的数据映射到一定的小范围内。缺点是可能出现冲突，但可以用链表的方法解决。

几个常用质数：99991,10007，131，13331。

10003不是质数。它等于7*1429；10007是，但100007不是，它等于97*1031；

字符串Hash

可以把字符串看做一个P进制的数，通过数的运算可以比较字符串字典序（先通过二分找到最长前缀，然后比较最长前缀的下一个数）。

例如，CH_1402 后缀数组

在结尾都相同时，可以这样写：

inline bool cmp(int a,int b){
     int mid,l=0,r=min(len-a+1,len-b+1);
     while(l>1;
         if(eql(a,a+mid-1,b,b+mid-1)){//记得-1 求的是长度
             l=mid;
         }
         else r=mid-1;
     }
     return s[a+l]<s[b+l];
 }

如果结尾不同，在等于它们其中任意一个字符串的长度时，和可能访问到其它字符（如果都保存在同一个字符数组里的话）。

如果要求最长前缀的话也可以这样写，直接将返回类型bool改为int，并且返回l即可。

字符串哈希也可以用于比较两段字符串大小：

inline bool eql(int l1,int r1,int l2,int r2){
      return f[r1]-f[l1-1]p[r1-l1+1]==f[r2]-f[l2-1]p[r2-l2+1];
}

如果要判断回文串，可以从前往后、从后往前分别开两个数组记录字符串的Hash。求最长回文串还有一个马拉车（）算法，找时间去研究一下。

随手写的，可能没有阅读体验，仅供自己学习。

以后遇到再来补充。