字符串hash算法，附图片理解

字符串hash算法

字符串hash是指将一个字符串s映射为一个，使得该整数可以尽可能唯一的代表也就是唯一标识。换言之，如果两个字符的hash值相同那么我们可以认为两者相同。

如果，我们对字母a~z进行一些的处理(如上图),但是aba的hash值和baa的hash值是一样的，这样子不可以唯一区分。

我们就要想办法将这个hash值变为唯一区分的

这个图前面序列之和*8等于后面序列之和。

重点来了：
	我们通过乘以某个数字不断增大。某一个段相同序列必定是相同一段的倍数。
	只要知道这个倍数就知道了这个序列是不是一样的。
           

如果不记录倍数的话，只我们容易出现这种情况，这种翻车情况还是有。

但是我们如果以指数相加，必须取余某一个数字，但是这个增加了翻车机率。

我们希望我们有的数，尽可能的出现差错的可能性小一点。
	其实很容易猜到如果选取2作为作为倍数进行去的话，很有可能出现相同hash值不同的列。
	资料说：一般来说P最好为素数，而且大一点好，基本上都是设置成为133左右的数字，模尽可能取大一点，翻车概率会小很多。
           

#include<iostream>
#include<algorithm>
using namespace std;
const long long int N = 1500000;
unsigned long long int pownum[N], hashnum[N];//前面一个是倍数,后面是折算值
//用unsigned可以自动取模。2^64-1
int base = 133;
unsigned long long get(int l, int r) {      //求一段区间的哈希值
	return hashnum[r] - hashnum[l - 1] * pownum[r - l + 1];
}

int main()
{
	char str[N];
	scanf("%s", str + 1);
	pownum[0] = 1;
	for (int i = 1; i < strlen(str); i++)
	{
		hashnum[i] = (str[i] - 'a' + 1) + hashnum[i-1] * base;
		pownum[i] = pownum[i-1] * base;
	}

}