今天想学字符串hash是怎么弄的。就看到了这题模板题
http://acm.hdu.edu.cn/showproblem.php?pid=4622
刚开始当然不懂啦，然后就上网搜解法。很多都是什么后缀自动机那些。作为小白的我当然不懂啦，更重要的是我想学的是字符串hash这种解法呢？然而有这种解法，但是却都是只有代码，看起来很辛苦。所以这里我把我的理解写上来，当然有错误的话，请各路高手指出来，我也好好学习下~~
首先介绍一个字符串Hash的优秀映射函数：BKDRHash，这里hash一开始是等于0的
for(i=1 to lenstr) hash = seed * hash + str[i]; 这是求解hash值的公式。绝大多数情况下能唯一确定字符串。seed是一个参数，一般取 31 、131、 1313、 13131、 131313、 etc..冲突比较小
经典题目：HDU 4622 Reincarnation
题意：给定一个长为2000个字符串，给出Q(Q<=10000)个询问。每个询问包含[L,R]，要求算出这个区间内不同的子串的个数。
思路：暴力枚举区间长度L，从1开始枚举到lenstr，再枚举起点i即可。能在O(n2)的时间枚举完。但仅仅是枚举完，但这里并没有去重，这部分时间，我们用hash来完成，复杂度压到O(1)。什么叫去重呢？例如baba,当我们枚举第二个ba的时候，就要告诉我们”ba”在[1,4]中重复出现了一次，所以ans[1][4]--; //ans[L][R]就是表示区间内不同子串的个数了。
要枚举那么多子串，我们希望，对于任意给定的区间[L,R]，都能快速地算出它的hash值是多少。例如求[3,4]的hash值，明显有 ans = seed * str[3] + str[4];（这是根据公式得到的。）
那么我们先预处理一个前缀hash总和，记为sumHash[i]表示1~i的hash值。则有
sumHash[1] = str[1]; sunHash[2] = seed * str[1] + str[2];
sunHash[3] = seed * sumHash[2] + str[3]; sumHash[4] = seed * sumHash[3] + str[4];
把他们拆出来，即可得到[3,4] ans = sumHash[4] – seed(R-L+1) * sumHash[2];
所以预处理两个数组，powseed[i]表示seed的i次方， sumHash[i]定义如上
然后就是怎么判断重复出现的问题了。我们知道那个hash值是唯一的，我们只能靠这个来判断是否重复出现，但是这个hash值很大，用map<ULL,int>来模拟是可以得，但是很慢。怎么办呢?我们可以用图，先把hash值%MOD压缩下，把他们加入到一幅图中，再开一个数组保存边的权值，用边的权值来和hash值判断相不相同，即可确定是否重复出现。
那个图没什么了不起的，就是为了返回出现的位置，不要被那个图吓到了。
下面代码可以300+ms
#include <cstdio>
#include <cstdlib>
#include <cstring>
typedef unsigned long long int ULL;
//BKDRHash，最优的字符串hash算法。hash一开始是等于0的
//for(i=1 to lenstr) hash = seed * hash + str[i]; 这是求解hash值的公式
//我们希望，对于任意给定的区间[L,R]，都能快速地算出它的hash值是多少
//明显我们要算的是：例如[3,4] ans = seed * str[3] + str[4]
//那么我们先预处理一个前缀hash总和，记为sumHash[i]表示1~i的hash值
//sumHash[1] = str[1]; sunHash[2] = seed * str[1] + str[2];
//sunHash[3] = seed * sumHash[2] + str[3]; sumHash[4] = seed * sumHash[3] + str[4];
//拆出来，得到若要求[3,4] 既可以 ans = sumHash[4] - seed^(R-L+1) * sumHash[2]
//所以预处理两个数组，powseed[i]表示seed的i次方， sumHash[i]定义如上
const int seed = ; // 31 131 1313 13131 131313 etc..
const int maxn = +;
char str[maxn];
ULL powseed[maxn]; // seed的i次方 爆了也没所谓，sumHash的也爆。用了ULL，爆了也没所谓，也能唯一确定它，无符号
ULL sumHash[maxn]; //前缀hash值
int ans[maxn][maxn]; //ans[L][R]就代表ans,就是区间[L,R]内不同子串的个数
const int MOD = ;
struct StringHash
{
int first[MOD+],num; // 这里因为是%MOD ，所以数组大小注意，不是maxn
ULL EdgeNum[maxn]; // 表明第i条边放的数字(就是sumHash那个数字)
int next[maxn],close[maxn]; //close[i]表示与第i条边所放权值相同的开始的最大位置
//就比如baba，现在枚举长度是2，开始的时候ba，close[1] = 1;表明"ba"开始最大位置是从1开始
//然后枚举到下一个ba的时候，close[1]就要变成3了，开始位置从3开始了
void init ()
{
num = ; memset (first,,sizeof first);
return ;
}
int insert (ULL val,int id) //id是用来改变close[]的
{
int u = val % MOD; //这里压缩了下标，val是一个很大的数字，这里就有一个问题了，val是唯一的，因为它是从sumHash得到的
//那个hash算法很优秀，基本上val是唯一的了。现在我们想知道和val值相同的地方是哪里。又是上面那个例子了。baba。当我们
//枚举第二个ba的时候，我想知道它有没出现过，如果有，请放回它出现的位置。这里其实完全可以用map<ULL,int>book这样做，
//如果book[val] != 0，就代表出现过了，更新，返回就可以。但是非常慢，2800+ms,第二次提交还TLE
//所以我们逼不得已用图了，再加上其他辅助的数组.EdgeNum[]就是用来判断和val相不相同的。这样时间才降下来
for (int i = first[u]; i ; i = next[i]) //存在边不代表出现过，出现过要用val判断，val才是唯一的，边还是压缩后(%MOD)的呢
{
if (val == EdgeNum[i]) //出现过了
{
int t = close[i]; close[i] = id;//更新最大位置
return t;
}
}
++num; //没出现过的话，就加入图吧
EdgeNum[num] = val; // 这个才是精确的
close[num] = id;
next[num] = first[u];
first[u] = num;
return ;//没出现过
}
}H;
void work ()
{
scanf ("%s",str+);
int lenstr = strlen(str+);
for (int i=;i<=lenstr;++i)
sumHash[i] = sumHash[i-]*seed + str[i];
memset(ans,,sizeof(ans));
for (int L=;L<=lenstr;++L) //暴力枚举子串长度
{
H.init();
for (int i=;i+L-<=lenstr;++i)
{
int pos = H.insert(sumHash[i+L-]-powseed[L]*sumHash[i-],i);
ans[i][i+L-] ++;//ans[L][R]++，自己是一个
ans[pos][i+L-]--;//pos放回0是没用的
//就像bababa，第二个ba的时候，会ans[1][4]--;表明[1,4]重复了一个
//然后第三个ba的时候，ans[2][6]--,同理，表明[2,6]也是重复了
//那么ans[1][6]重复了两个怎么算？就是在递推的时候，将ans[2][6]的值覆盖上来的
//ans[1][6] += ans[2][6] + ans[1][5] - ans[2][5];
}
}
for (int i = lenstr; i>=; i--)
{
for (int j=i;j<=lenstr;j++)
{
ans[i][j] += ans[i+][j]+ans[i][j-]-ans[i+][j-];
}
}
int m;
scanf ("%d",&m);
while (m--)
{
int L,R;
scanf ("%d%d",&L,&R);
printf ("%d\n",ans[L][R]);
}
return ;
} int main ()
{
powseed[] = ;
for (int i = ; i <= maxn-; ++i) powseed[i] = powseed[i-] * seed;
int t;
scanf ("%d",&t);
while (t--) work();
return ;
}
下面再附上一个用map模拟的代码。2800+ms，可能会超时哦。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
typedef unsigned long long int ULL;
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
//BKDRHash，最优的字符串hash算法。hash一开始是等于0的
//for(i=1 to lenstr) hash = seed * hash + str[i]; 这是求解hash值的公式
//我们希望，对于任意给定的区间[L,R]，都能快速地算出它的hash值是多少
//明显我们要算的是：例如[3,4] ans = seed * str[3] + str[4]
//那么我们先预处理一个前缀hash总和，记为sumHash[i]表示1~i的hash值
//sumHash[1] = str[1]; sunHash[2] = seed * str[1] + str[2];
//sunHash[3] = seed * sumHash[2] + str[3]; sumHash[4] = seed * sumHash[3] + str[4];
//拆出来，得到若要求[3,4] 既可以 ans = sumHash[4] - seed^(R-L+1) * sumHash[2]
//所以预处理两个数组，powseed[i]表示seed的i次方， sumHash[i]定义如上
const int seed = ; // 31 131 1313 13131 131313 etc..
const int maxn = +;
char str[maxn];
ULL powseed[maxn]; // seed的i次方 爆了也没所谓，sumHash的也爆。用了ULL，爆了也没所谓，也能唯一确定它
ULL sumHash[maxn]; //前缀hash值
int ans[maxn][maxn]; //ans[L][R]就代表ans,就是区间[L,R]内不同子串的个数
const int MOD = ;
struct StringHash
{
//int book[MOD+20];
map<ULL,int>book;
void init ()
{
book.clear(); return ;
}
int insert (ULL val,int id)
{
if (book[val])
{
int t = book[val];
book[val] = id;
return t;
}
book[val] = id;
return ;
}
}H;
void work ()
{
scanf ("%s",str+);
int lenstr = strlen(str+);
for (int i=;i<=lenstr;++i)
sumHash[i] = sumHash[i-]*seed + str[i];
memset(ans,,sizeof(ans));
for (int L=;L<=lenstr;++L) //暴力枚举子串长度
{
H.init();
for (int i=;i+L-<=lenstr;++i)
{
int pos = H.insert(sumHash[i+L-]-powseed[L]*sumHash[i-],i);
ans[i][i+L-] ++;//ans[L][R]++，自己是一个
ans[pos][i+L-]--;//pos放回0是没用的
//就像bababa，第二个ba的时候，会ans[1][4]--;表明[1,4]重复了一个
//然后第三个ba的时候，ans[2][6]--,同理，表明[2,6]也是重复了
//那么ans[1][6]重复了两个怎么算？就是在递推的时候，将ans[2][6]的值覆盖上来的
//ans[1][6] += ans[2][6] + ans[1][5] - ans[2][5];
}
}
for (int i = lenstr; i>=; i--)
{
for (int j=i;j<=lenstr;j++)
{
ans[i][j] += ans[i+][j]+ans[i][j-]-ans[i+][j-];
}
}
int m;
scanf ("%d",&m);
while (m--)
{
int L,R;
scanf ("%d%d",&L,&R);
printf ("%d\n",ans[L][R]);
}
return ;
} int main ()
{
#ifdef local
freopen("data.txt","r",stdin);
#endif
powseed[] = ;
for (int i = ; i <= maxn-; ++i) powseed[i] = powseed[i-] * seed;
int t;
scanf ("%d",&t);
while (t--) work();
return ;
}