字符串哈希介绍

字符串HASH

字符串哈希算是哈希的一个小分支吧。。
hash，又叫散列表，即对一个数据(整数，或字符串等)通过散列函数转化成一个不易重复的，可以通过O(1)复杂度直接来访问的整数(或其他)。
字符串hash，通俗来讲，就是把一个字符串转换成一个整数，这种转换是一种一一映射。转换的方式就是散列函数。竞赛中常用的散列函数为进制法。hash(i) = hash(i-1)*base+s[i]，这是最常见的，即以进制的方式对一个字符串进行hash，其中base为进制的基，这个数通常很大，因此一般对一个大质数取模来存储。当两个字符串的哈希值相同时，就发生了散列冲突。
为了解决这种情况，我们尽可能的使散列函数为一一映射，通常，基数base取质数131，或者1331，模数取一大质数1e9+7,1e9+7等，也可以直接使用ull自然溢出(补充：unsigned类型整数，当数值大小超出数据类型范围时，最终结果为实际数值对该数据类型的最大数取模的结果，即ull溢出后，结果是对2^{64}取模的值)。这是单hash方法。
双hash其实就是取两个base，取两个mod，然后得到两个hash值，用这值个hash值组成的一个二元组来作为这个字符串的hash，这种方法基本不会出错。
获取子串l~r的hash：

hash[l..r] = hash[r] - hash[l-1]*pow(base,l-r+1)

这个一定要记住，熟练。
下面是N*M二维矩阵匹配的模板

#include <cstdio>
using namespace std;
typedef unsigned long long ull;
const ull maxn = 1005,base1 = 131,base2 = 1331;
ull N,M,X,Y;
char s[maxn][maxn],t[105][105];
ull w1[maxn][maxn],temp[maxn][maxn],w2[105][105],pow_mod1[105],pow_mod2[105];
void init();
int main(){
    init();
    int T,ans;
    scanf ("%d",&T);
    while (T--){
        ans = 0;
        scanf ("%d %d",&N,&M);
        if (N && M)
            for (int i=1;i<=N;i++)  scanf ("%s",s[i]+1);
        scanf ("%d %d",&X,&Y);
        if (X==0 || Y==0 || N==0 || M==0){
            printf("0\n");
            continue;
        }
        for (int i=1;i<=X;i++)  scanf ("%s",t[i]+1);
        if (X>N || Y>M){
            printf("0\n");
            continue;
        }
        for (int i=1;i<=N;i++){
            for (int j=1;j<=M;j++)  w1[i][j] = w1[i][j-1]*base1+s[i][j];
            for (int j=1;j<=M-Y+1;j++)  temp[i][j] = w1[i][j+Y-1]-w1[i][j-1]*pow_mod1[Y];
        }
        for (int j=1;j<=M-Y+1;j++){
            for (int i=1;i<=N;i++)  temp[i][j] = temp[i-1][j]*base2+temp[i][j];
            for (int i=1;i<=N-X+1;i++)  w1[i][j] = temp[i+X-1][j] - temp[i-1][j]*pow_mod2[X];
        }
        for (int i=1;i<=X;i++){
            for (int j=1;j<=Y;j++)  w2[i][j] = w2[i][j-1]*base1+t[i][j];
            w2[i][Y] = w2[i-1][Y]*base2+w2[i][Y];
        }
        for (int i=1;i<=N-X+1;i++)  for (int j=1;j<=M-Y+1;j++)
            if (w1[i][j]==w2[X][Y]) ans++;
        printf("%d\n",ans);
    }
    return 0;
}
void init(){
    pow_mod1[1] = base1,pow_mod2[1] = base2;
    for (int i=2;i<=100;i++){
        pow_mod1[i] = pow_mod1[i-1]*base1;
        pow_mod2[i] = pow_mod2[i-1]*base2;
    }
    return;
}