01、BKDRHash哈希函数

1. 字符串哈希函数

首先看一个比较特殊的字符串匹配问题： 在很多字符串中，尽快操作某个字符串，如查询、修改等。如果字符串的规模很大，访问速度很关键。这个问题用哈希解决是最快的。用哈希函数对每个子串进行哈希，分别映射到不同的数字，即一个整数哈希值，然后根据哈希值找到子串。

哈希函数是算法的核心。理论上任意函数h(x)都可以是哈希函数，不过一个好的哈希函数应该尽量避免冲突。这个字符串哈希函数最好是完美哈希函数。完美哈希函数是指没有冲突的哈希函数： 把n个子串的key值映射到m个整数上，如果对任意的key1≠key2，都有h(key1)≠h(key2)，这就是完美哈希函数。此时必然有n≤m，特别地，如果n=m，称为最小完美哈希函数。

如何找到一个好的字符串哈希函数？有一些经典的字符串哈希函数，如BKDRHash、APHash、DJBHash、JSHash等。其中最好的是BKDRHash，计算的哈希值几乎不会冲突碰撞。另外，由于得到的哈希值都很大，不能直接映射到一个巨大的空间上，所以一般都需要限制空间。方法是取余，把得到的哈希值对一个设定的空间大小M取余数，以余数作为索引地址。当然，这样做可能产生冲突问题。

编程时可以采用一种“隐性取余”的简化方法。取空间大小为M=264，64是unsigned long long型的长度，一个unsigned long long型的哈希值H，当H>M时会自动溢出，等价于自动对M取余，这样能避免低效的取余运算。

2. BKDRHash

BKDRHash是一种“进制哈希”，计算步骤非常简单。设定一个进制P，需要计算一个字符串的哈希值时，把每个字符看作每个进制位上的一个数字，这个串转换为一个基于进制P的数，最后对M取余数，就得到了这个字符串的哈希值。

例如，计算只用小写字母组成的字符串的哈希值，以字符串abc为例，令进制P=131，有以下两种方法。

(1) 把每个字符看作一个数字，即a=1，b=2，c=3，…，z=26，然后把字符串的每位按进制P的权值相加得： 'a'×1312+'b'×1311+'c'×1310=1×1312+2×1311+3×1310=17426。不需要再除M取余，原因在前面已解释，即大于M时溢出，自动取余。

(2) 直接把每个字符的ASCII码看作代表它的数字也可以，计算得： 'a'×1312+'b'×1311+'c'×1310=97×1312+98×1311+99×1310=1677554。

进制P常用的值有31、131、1313、13131、131313等，用这些数值能有效避免碰撞。

3. 模板代码

用下面的例题给出BKDRHash的代码。
● 例9.1【模板】字符串哈希(洛谷 P3370)

题目描述：给定N个字符串，第i个字符串长度Mi，字符串内包含数字和大小写字母。求N个字符串中共有多少个不同的字符串。

ull BKDRHash(char *s)函数生成字符串s的哈希值并返回。代码第9~10行计算权值之和，注意代码的写法，第10行给出了上述两种方法。另外，把第8~10行改写成第12行，效果一样。

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
ull a[10010];
char s[10010];
ull BKDRHash(char *s){             //哈希函数
    ull P = 131, H = 0;            //P是进制，H是哈希值
    int n = strlen(s);
    for(int i=0;i<n;i++)
        H = H * P + s[i]-'a'+1;    //H = H * P + s[i];  //两种方法
 //上面三行可以简写为一行：
 // while(*s)   H = H*P + (*s++);
    return H;                      //隐含了取模操作，等价于 H % 264
}
int main(){
    int n; scanf("%d",&n);
    for(int i=0;i<n;i++) {
        scanf("%s",s);
        a[i] = BKDRHash(s);   //把字符串s的hash值记录在a[i]中
    }
    int ans = 0;
    sort(a,a+n);
    for(int i=0;i<n;i++)    //统计有多少个不同的hash值
        if(a[i]!=a[i+1])
            ans++;
    printf("%d",ans);
}

02、进制哈希的应用

由于进制哈希把字符串的每位看作一个数字，所以字符串的各种操作对应的哈希计算都能按P进制数的运算规则进行。设字符串S的哈希值为H(S)，长度为len(S)。以两个字符串的组合为例，两个字符串的组合S1+S2的哈希值为H(S1)×Plen(S2)+H(S2)。其中，乘以Plen(S2)相当于左移了len(S2)位。例如，S1=“abc”，S2=“xy”，S1+S2=“abcxy”的哈希值等于H(abc)×P2+H(xy)。

利用进制哈希可以按进制做算数运算的这个特征，能用来快速计算字符串S的所有前缀。例如,S=“abcdefg”，它的前缀有{a，ab，abc，abcd，…}。计算过程如下。

(1) 计算前缀a的哈希值，得H(a)，计算时间为O(1)。

(2) 计算前缀ab的哈希值。H(ab)=H(a)×P+H(b) ，计算时间为O(1)。

(3) 计算前缀abc的哈希值。H(abc)=H(ab)×P+H(c) ，计算时间为O(1)，等等。

只需一个for循环遍历S，就能在O(n)的时间内预处理所有前缀的哈希值。

计算出S的所有前缀的哈希值后，能以O(1)的复杂度查询它的任意子串的哈希值，如H(de)=H(abcde)-H(abc)×P2。求区间［L，R］的哈希值的代码可以这样写(其中P［i］表示P的i次方)：

ull get_hash(ull L, ull R) { return H[R] - H[L - 1] * P[R - L + 1]; }

很多字符串问题和前缀、后缀有关，如回文串问题、字符串匹配问题等。利用进制哈希，能以不错的时间复杂度求解。虽然效率比KMP、Manacher等经典算法差一些，占用空间也大一些，但是一般情况下够用。下面给出两个例子。

1. 进制哈希与最长回文串

查找一个长度为n的字符串S中的最长回文子串，标准解法是Manacher算法，复杂度为O(n)。

用进制哈希求最长回文子串，复杂度为O(nlogn)，也是很好的解法。

一个回文串是正向读和反向读都相同的串，为了利用哈希找到这样的串，先预处理出字符串S的所有前缀的哈希值，再把S倒过来得T，预处理出T的所有前缀的哈希值。

如果S的某个子区间是一个回文串，那么对应T的子区间也是回文串，只要比较这两个区间的哈希值是否相等，就找到了一个回文串，一次比较的计算量为O(1)。例如，S=“abxyxc”，T=“cxyxba”，S的［2，4］区间是回文串“xyx”，对应T的［1，3］区间。

不过，如果简单地从头到尾遍历S的所有子区间，需O(n2)次。这里需要使用9.2节提到的“中心扩展法”： 以S的每个字符为中心，左右扩展，如果左右对应的字符相同，就是一个回文串。但是，如果简单地扩展，复杂度为O(n)，还是不够快。注意到扩展中心字符的左右求回文串的长度具有单调性，可以用二分法加速。

概括进制哈希求解最长回文串的步骤： 遍历S的每个字符，遍历到第i个字符时，以它为中心，用二分法扩展它的左右两边，用哈希判断这个区间是否为回文串。共n个字符，向每个字符左右扩展的二分复杂度为O(logn)，一次哈希判断复杂度为O(1)，总复杂度为O(nlogn)。

注意，上面对回文串的判断，有点小问题。回文串长度是奇数时，可以用中间字符为中心扩展左右两边，如“xyx”的中间字符是“y”。如果回文串长度是偶数，如“xyyx”，那么就没有中间字符。解决方案见下一节的“中心扩展法”。

提示/
回文串的题目一般用Manacher算法求解，但是由于“进制哈希+二分”的思路很简单，编码快。

● 例9-2. ANT-Antisymmetry 洛谷P3501

题目描述：对于一个01字符串，如果将这个字符串0和1取反后，再将整个串反过来和原串一样，就称作“反对称”字符串。比如00001111和010101就是反对称的，1001就不是。现在给出一个长度为N的01字符串，求它有多少个子串是反对称的。不同位置的相同回文串需要重复统计。

输入：第一行是字符的长度n，第二行是一个只包含0和1的字符串，没有空格。

输出：一个数字表示答案。

下面的代码用BKDRHash求哈希值，见第24和第25行。注意以下3个细节。

(1) 本题的回文串长度一定是偶数。题目中“整个串反过来和原串一样”，那么这样的回文串长度肯定是偶数，如S=0011，反串T=1100，S符合要求。但是，像S=100这样的长度为奇数的串肯定不符合要求，因为它的反串T=011的中间字符与S的中间字符相反。

(2) 判断回文。代码第14行判断左半部分［x-mid，x］和右半部分［x+1，x+1+mid］是否相等。本题的回文串没有中间字符。

(3) bin_search()函数用二分法找以s［x］为中心的回文串，L是以s［x］为中心。找到的最长回文串是［x-mid，x］加［x+1，x+1+mid］，它的半径是mid。L=mid，在这个最长回文串内部共有L个回文串。

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N = 5e5+10;
char s[N],t[N];
int n,PP =131;
long long ans; 
ull P[N],f[N],g[N];         //P：计算p的i次方，f：s的前缀哈希值，g：t的前缀哈希值
void bin_search(int x){     //用二分法寻找以s[x]为中心的回文串
     int L=0,R=min(x,n-x);    
     while(L<R){
         int mid = (L+R+1)>>1;
         if((ull)(f[x]-f[x-mid]*P[mid])==(ull)(g[x+1]-g[x+1+mid]*P[mid]))  L = mid;
         else R = mid-1;
  }
  ans += L;              //最长回文串的长度是L，它内部有L个回文串
}
int main(){
    scanf("%d",&n);   scanf("%s",s+1);
    P[0] = 1;
    for(int i=1;i<=n;i++)  s[i]=='1'? t[i]='0':t[i]='1'; //t是反串
    for(int i=1;i<=n;i++)  P[i] = P[i-1]*PP;             //P[i]=PP的i次方
    for(int i=1;i<=n;i++)  f[i] = f[i-1]*PP + s[i];      //求s所有前缀的哈希值
    for(int i=n;i>=1;i--)  g[i] = g[i+1]*PP + t[i];      //求t所有前缀的哈希值
    for(int i=1;i<n;i++)   bin_search(i); 
    printf("%lld\n",ans);
    return 0;
}

2. 进制哈希与循环节

下面例题的标准解法是KMP算法，复杂度为O(n)。这里用进制哈希求解，复杂度非常接近O(n)。
● 例9.3最短循环节问题(洛谷P4391)

问题描述： 字符串S1由某个字符串S2不断自我连接形成，但是字符串S2未知。给出S1的一个长度为n的片段S，问可能的S2的最短长度是多少？例如，给出S1的一个长度为8的片段P=“cabcabca”，求最短的S2长度，答案是3，S2可能是“abc”“cab”“bca”等。

先预处理出S的所有前缀的哈希值，用于求区间哈希值。代码的流程非常简单，当遍历到i时，用暴力验证区间［1，i］是否为循环节即可，即比较后面每个区间是否与［1，i］的哈希值相同，如果都相同，就是循环节，如果有一个不同，这轮验证结束。复杂度接近O(n)。

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N = 1e6+100;
ull PP = 131;
char s[N];
ull P[N],H[N],n;
ull get_hash(ull L,ull R){return H[R]-H[L-1]*P[R-L+1];}     //区间[L,R]的哈希值
int main(){
    P[0]=1;
    for(int i=1; i<=N-1; i++)   P[i] = P[i-1]*PP;  //预处理PP的i次方
    cin>>n;  scanf("%s",s+1);                      //s[0]不用
    for(ull i=1; i<=n; i++)  H[i] = H[i-1]*PP + s[i]; //预处理所有前缀的hash值
    for(ull i=1; i<=n; i++) {
        ull flag = 1;
        ull last = get_hash(1,i);                 //暴力验证区间[1,i]是否为循环节
        for(int j=1; (j+1)*i<=n; j++) {           //一个区间一个区间地判断
            if(get_hash(j*i+1,(j+1)*i)!=last){    //这一区间是否与第一区间相同
               flag=0;
               break;
            }
        }
        if(n*I != 0){                             //末位多了一小截，单独判断
      ull len = n%i;
      if(get_hash(1,len) != get_hash(n-len+1,n))   flag=0;
    }
    if(flag){ printf("%d\n",(int)i); break;}    //找到了答案，输出然后退出
  }
  return 0;
}