字符串hash
一个hash方法，BKDRHash。
选定一个seed，然后求一个字符串的hash值
for(int i=1; i<strlen; i++) hash = hash*seed + str[i]这里hash初始化为0
这样就求出了字符串str的hash值，seed的取值可以是13131 13331这种，碰撞较少。
给定一个字符串str怎么求它每一个子串的hash呢？
我们可以预处理一个前缀和sumhash[i]表示1~i这一段字符串的hash值,对于str
sumhash[1] = srt[1]，sumhash[2] = seed*srt[1] + str[2]
sumhash[3] = seed*sumhash[2] + srt[3]，sumhash[4] = seed*sumhash[3] + srt[4]
如果想得到[L,R]这个子串的hash,
hash = sumhash[R] - seed^(R-L+1) * sumhash[L-1]
例如区间[3,4]，hash = sumhash[4] - seed^2 * sumhash[2]
= (seed * sumhash[3] + srt[4]) - (seed^2 * sumhash[2])
= (seed^2 * sumhash[2] + seed*str[3] + str[4]) - (seed^2 * sumhash[2])
= seed * str[3] + str[4],符合BKDRHash方法求出的值
例题
HDU4622
题目大意
给你一个字符串，然后有多组询问，问你在[L,R]区间有多少个不同子串
例如str = "bbaba",
区间[1,1]的子串有1个"b"
区间[1,2]的子串有2个"b","bb"
区间[3,4]的子串有3个"a","b","ab"
思路
先构造sumhash,这样就可以O(1)得出任意子串的hash
用ans[L][R]存储区间不同字串的个数，模拟一个map用来判断某个子串是否出现过，暴力枚举区间，计算个数。
#include <stdio.h>
#include <string.h>
const int seed = 13131;
const int MOD = 10007; //映射位置 %MOD
const int MAXN = 2010; //比字符串长度大
unsigned long long powseed[MAXN];
unsigned long long sumhash[MAXN];
char str[MAXN];
namespace HASHMAP{//功能类似map<ull,int>,查询子串最大出现位置
int first[MOD], num; //存放sumhash映射后的位置
unsigned long long EdgeNum[MAXN]; //存放精确sumhash，num数组len
int next[MAXN], close[MAXN]; //close[i]表示子串(sumhash)出现过的最大位置
void init(){
num = 0;
memset(first,0,sizeof(first));
}
int insert(unsigned long long val, int id){//val是sumhash，id是子串开始位置
int u = val % MOD; //val是一个子串的hash，不同子串hash可看最唯一的，压缩下标
for(int i=first[u]; i; i=next[i]){//这个子串可能出现过，first值为0表示没出现过，
//next是碰撞处理，压缩下标会产生碰撞
if(val == EdgeNum[i]){//确实出现过，EdgeNum存的才是精确hash
int t = close[i];
close[i] = id;//更新最大位置
return t;
}
}
//没有出现的话
++num;
EdgeNum[num] = val;
close[num] = id;
next[num] = first[u];
first[u] = num;
return 0;
}
}
int ans[MAXN][MAXN];
void work(){
scanf("%s",str+1);
int lenstr = strlen(str+1);
for(int i=1;i<=lenstr;++i){
sumhash[i] = sumhash[i-1]*seed + str[i];
}
memset(ans, 0, sizeof(ans));
for(int L=1;L<=lenstr;++L){//枚举长度
HASHMAP::init();
for(int i=1; i+L-1<=lenstr; ++i){//枚举开始位置
int pos = HASHMAP::insert(sumhash[i+L-1]-powseed[L]*sumhash[i-1],i);
ans[i][i+L-1]++; //ans[l][r]区间内的不同串个数++，中间数据
ans[pos][i+L-1]--; // pos为0的时候没有意义，pos<i
//如“bababa”，枚举到第二个“ba”时候，ans[1][4]--;代表[1,4]重复一个
//枚举到第三个“ba”shihou ,ans[2][6]--,表示[2,6]重复一个
//对于ans[1][6]重复两个，怎么算？
//ans[1][6] += ans[2][6] + ans[1][5] - ans[2][5];
}
}
for(int i=lenstr; i>=1; i--){
for(int j=i; j<=lenstr; j++){
ans[i][j] += ans[i+1][j] + ans[i][j-1] - ans[i+1][j-1];
//处理后ans[i][j],就是区间内不同子串的个数
//转移方程需要i+1和j-1的状态
}
}
int t;
scanf("%d",&t);
while(t--){
int l,r;
scanf("%d %d",&l,&r);
printf("%d\n",ans[l][r] );
}
}
int main(){
powseed[0]=1;
for(int i=1; i<MAXN;++i){
powseed[i] = powseed[i-1] * seed;
}
int t;
scanf("%d",&t);
while(t--) work();
return 0;
}
