哈希前缀和

1.前言

很早之前听说了这个算法，上个暑假zyz学长教会了我，前一阵字考试用到了差点忘记怎么写，好像这个方法知道的人也不多，特地写一写

2.哈希前缀和

哈希前缀和，顾名思义就是哈希算法和前缀和结合起来。我们都知道哈希能够将一段字符串转换成一个整数，由此可以判断两段字符串是否相等例如模板题:P3370 【模板】字符串哈希。
但其实仅仅如此的话哈希算法的用处还是有限的，因为比较简单的情况下可以使用set等等STL容器可以一定程度上替代他的功能，比较复杂的操作可以用 字典树 加上 树形dp 来解决。但是对于很多不熟悉STL的人来说不失为一个好办法。
但是如果哈希和前缀和联系起来他的用处就大多了，有了它你甚至不需要学复杂的KMP。
对于普通的哈希算法而言：

1
2
3
4
5
6
7
8
9
10

inline int hash(const int l,const int r){
   for(int i=l;i<=r;i++){
      res=res*base+s[i];    //一般情况下base选用131，当然也可以是其他
      res%=p;
      return res;
   }
   //p是一个比较大的数，一般选用大质数，但实际上如果你懒得模  
   //完全可以选择自然溢出，冲突的关键在于base而不是模数
   //例如 unsigned long long res;完全没有必要去 mod p了
}

这样子就可以很容易的得到一段字符串的哈希值了
但是这样时间复杂度是o(n),有没有可能o(1)呢，观察代码我们发现，如果有一个字符串 s 你想知道 s[1]s[5],s[2]s[6] 的哈希值，你发现其中的 s[2]~s[5] 的哈希值被重复计算了。自然我们想用前缀和优化。

3.代码：

1
2
3
4
5
6
7
8

inline void hash(const int l,const int r){
	for(int i=r;i>=l;i--){
		h[i]=h[i+1]*131+s[i];
	}
}
inline void get(const int l,const int r){
	return h[l]-h[r]*base[r-l+1];
}