贵阳建立网站,市场推广有哪些,wordpress修改主题模板,福建建设网站ACM模板 目录构建应用构建 字符串哈希就是将字符串映射成一个数#xff0c;哈希冲突是不可避免的#xff0c;我们需要选用合适的base尽可能使得哈希冲突可能性降低 unsigned long long溢出后相当于取模#xff0c;相当于模264−12^{64}-1264−1 get(l,r)函数返回字符串下标…ACM模板 目录构建应用构建 字符串哈希就是将字符串映射成一个数哈希冲突是不可避免的我们需要选用合适的base尽可能使得哈希冲突可能性降低 unsigned long long溢出后相当于取模相当于模264−12^{64}-1264−1 get(l,r)函数返回字符串下标[l,r]的哈希值 typedef unsigned long long ull;
const int N100010,P131;//13331 19260817 防止哈希冲突
ull h[N],p[N];
ull get(int l,int r)
{return h[r]-h[l-1]*p[r-l1];
}
void build(char s[])
{int nstrlen(s1);p[0]1;for(int i1;in;i){p[i]p[i-1]*P;h[i]h[i-1]*Pstr[i]-a1;}
}应用
暴力字符串匹配优化字符串字典序比较——二分哈希通常可以二分最长公共前缀然后比较公共前缀的下一个字符即可以知道字典序。log求最长回文串首先将原串和逆序串哈希枚举回文中心二分回文半径记录一些dp的状态
