字符串哈希可以快速判断两个子字符串是否相等
原理:https://www.cnblogs.com/ydUESTC/p/15722400.html
注意 字符串哈希时后面的字符视为低位,这样方便取一段字符的哈希时先做乘法再做减法。
例题:https://leetcode.cn/problems/maximum-deletions-on-a-string/
模板:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
typedef unsigned long long ULL; const int N=4010,P=131;//P=131或13331 ULL h[N];//预处理出哈希数组 ULL p[N];//预处理P^i数组 ULL Get(int l,int r) { return h[r]-h[l-1]*p[r-l+1]; } cin>>str; int n=str.size(); p[0]=1; for(int i=1;i<=n;i++) { p[i]=p[i-1]*P; h[i]=h[i-1]*P+str[i-1];//注意这里,最新的字符视为str[i-1]*P^0 }View Code
标签:哈希,int,ULL,字符串,例题,模板 From: https://www.cnblogs.com/ydUESTC/p/16755762.html