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];
}

如果结尾不同,在l等于它们其中任意一个字符串的长度时,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。求最长回文串还有一个马拉车(Manacher)算法,找时间去研究一下。

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

以后遇到再来补充。

留下评论

您的电子邮箱地址不会被公开。