10.11 Hash进阶-回文串

· · 算法·理论

Hash进阶操作

Hash基础：9.27 字符串哈希-Hash

Hash进阶求回文串需要在从左到右求Hash值的同时从右到左在求一边Hash值最后对比从左到右和从右到左是否相等，如果相等就是回文

求Hash函数

依然使用进制求法

从左到右

    for(int i(1);i<=n;i++){
        hs1[i]=hs1[i-1]*p+s[i];
    }

从右到左

    for(int i(n);i>0;i--){
        hs2[i]=hs2[i+1]*p+s[i];
    }

计算区间[l,r]的Hash值

从左到右

注意到因为Hash_i储存的使字符串前i个字符的Hash值，所以我们可以把Hash数组当作一个前缀和数组来看待

[l,r]的Hash值=Hash_r-Hash_{l-1}

但Hash值是一个p进制的数，而不是前缀和，举个十进制数的例子：

如果只是像前缀和一样直接减去的话就成了$123456-123$很明显不对，应该是$123456-123000$，这样才能求出$456$，将这个式子转换一下就成了$123456-123\times10^3$，而指数$3$很明显就是$456$的长度 现在我们回到Hash上，答案显而易见： [l,r]的Hash值=$Hash_r-Hash_{l-1}\times p^{(需要截取的长度)}=Hash_r-Hash_{l-1}\times p^{r-l+1} 
ull get_hash1(int l,int r){
    return hs1[r]-hs1[l-1]*pw[r-l+1];
}

从右到左

在考虑如何截取区间的Hash值前我们先模拟一下Hash数组的形成

当字符串为ABBA时

Hash_4=A\\ Hash_3=Hash_4\times p+B=A\times p+B\\ Hash_2=Hash_3\times p+B=A\times p^2+B\times p+B\\ Hash_1=Hash_2\times p+A=A\times p^3+B\times p^2+B\times p+C\\

即

Hash_4=A\\ Hash_3=A\times p+B\\ Hash_2=A\times p^2+B\times p+B\\ Hash_1=A\times p^3+B\times p^2+B\times p+C\\

很明显原来的公式不对了Hash_r<Hash_l如果使用减法就成负数了，既然不好想那我们又来举个例子：

如果我们要从ABBA中取出BB怎么办？

可以发现BB的Hash值在Hash_2中出现了B\times p+B只是多了一个A\times p^2这时我们发现Hash_4=A，所以我们只需要将Hash_2减去Hash_4\times p^2，而这时候我们又发现p^2中的指数与从左到右的意思相同，即需要取的长度，所以公式是：

[l,r]的Hash值=Hash_l-Hash_{r+1}\times p^{r-l+1}

ull get_hash2(int l,int r){
    return hs2[l]-hs2[r+1]*pw[r-l+1];
}