概述：
主要用于字符串的匹配。
定义hash函数：
H(c)=(c1bm-1 +c2bm-2 +...+cmb0)mod h
对于字符串c中l-r区间的hash值：
H(l,r)=H(1,r)-H(1,l-1)*br-l+1
如果hash值很大，对h取模，一般地，用unsigned long long 来保存数据，这样溢出时就会自动对264 取模。
如果两个字符串的hash值相等，我们认为它们相同，不排除小概率事件使得两个字符串具有相同的hash值（由取模导致）。
大白书例子：
const ull base=131;//a在b中是否出现bool contain(string a,string b){int al=a.length(),bl=b.length();if(al>bl)return false;//计算base的al次方ull t=1;for(int i=0;i<al;i++)t*=base;//计算a和b长度为al的前缀对应的hash值ull ah=0,bh=0;for(int i=0;i<al;i++)ah=ah*base+a[i];for(int i=0;i<al;i++)bh=bh*base+b[i];//对b不断的右移一位，更新hash值并判断for(int i=0;i+al<=bl;i++){if(ah==bh)return true;if(i+al<bl)bh=bh*base+b[i+al]-b[i]*t;}return false;}//a的后缀和b的前缀相等的最大长度int overlap(string a,string b){int al=a.length(),bl=b.length();int ans=0;ull ah=0,bh=0,t=1;for(int i=1;i<=min(al,bl);i++){ah=ah+a[al-i]*t;bh=bh*base+b[i-1];if(ah==bh)ans=i;t*=base;}return ans;}
HDU - 4300
代码：
#include<bits/stdc++.h>using namespace std;#define ll long long#define pb push_back#define ull unsigned long long#define mem(a,b) memset(a,b,sizeof(a))const ull base=131;int mp[26];int h(string s){int l=s.size();int mn=0;ull ph=0,sh=0,t=1;for(int i=0;i<l/2;i++){ph=ph*base+mp[s[i]-'a'];sh=(s[l-i-1]-'a')*t+sh;if(ph==sh)mn=i+1;t*=base;}for(int i=0;i<l-mn;i++)putchar(s[i]);for(int i=0;i<l-mn;i++)putchar(mp[s[i]-'a']+'a');puts("");}int main(){ios::sync_with_stdio(false);cin.tie(0);int T;string s,t;cin>>T;while(T--){cin>>t>>s;for(int i=0;i<26;i++)mp[t[i]-'a']=i;h(s);}return 0;}
