概述：

主要用于字符串的匹配。

定义hash函数：

H(c)=(c₁b^m-1 +c₂b^m-2 +...+c_mb⁰)mod h

对于字符串c中l-r区间的hash值：

H(l,r)=H(1,r)-H(1,l-1)*b^r-l+1

如果hash值很大，对h取模，一般地，用unsigned long long 来保存数据，这样溢出时就会自动对2⁶⁴ 取模。

如果两个字符串的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

 

代码：

#include
     
      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
      
       >T;    while(T--)    {        cin>>t>>s;        for(int i=0;i<26;i++)mp[t[i]-'a']=i;        h(s);    }    return 0;}