字元串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;
	}

}