字符串---hash

字符串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; 
}