专栏文章

10.11 Hash进阶-回文串

KKoei
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minmllel
此快照首次捕获于
2025/12/02 04:52
3 个月前
此快照最后确认于
2025/12/02 04:52
3 个月前
查看原文

Hash进阶操作

Hash基础：9.27 字符串哈希-Hash
Hash进阶求回文串需要在从左到右求Hash值的同时从右到左在求一边Hash值最后对比从左到右和从右到左是否相等，如果相等就是回文

求Hash函数

依然使用进制求法

从左到右

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

从右到左

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

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

从左到右

注意到因为HashiHash_i储存的使字符串前i个字符的Hash值，所以我们可以把Hash数组当作一个前缀和数组来看待
[l,r]的Hash值=Hashr−Hashl−1Hash_r-Hash_{l-1}
但Hash值是一个p进制的数，而不是前缀和，举个十进制数的例子：
123456123456要取456456怎么办？
如果只是像前缀和一样直接减去的话就成了123456−123123456-123很明显不对，应该是123456−123000123456-123000，这样才能求出456456，将这个式子转换一下就成了123456−123×103123456-123\times10^3，而指数33很明显就是456456的长度
现在我们回到Hash上，答案显而易见：
[l,r]的Hash值=Hashr−Hashl−1×p(需要截取的长度)=Hashr−Hashl−1×pr−l+1Hash_r-Hash_{l-1}\times p^{(需要截取的长度)}=Hash_r-Hash_{l-1}\times p^{r-l+1}
CPP
ull get_hash1(int l,int r){
	return hs1[r]-hs1[l-1]*pw[r-l+1];
}

从右到左

在考虑如何截取区间的Hash值前我们先模拟一下Hash数组的形成
当字符串为ABBAABBA时
Hash4=AHash3=Hash4×p+B=A×p+BHash2=Hash3×p+B=A×p2+B×p+BHash1=Hash2×p+A=A×p3+B×p2+B×p+CHash_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\\
即
Hash4=AHash3=A×p+BHash2=A×p2+B×p+BHash1=A×p3+B×p2+B×p+CHash_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\\
很明显原来的公式不对了Hashr<HashlHash_r<Hash_l如果使用减法就成负数了，既然不好想那我们又来举个例子：
如果我们要从ABBAABBA中取出BBBB怎么办？
可以发现BBBB的Hash值在Hash2Hash_2中出现了B×p+BB\times p+B只是多了一个A×p2A\times p^2这时我们发现Hash4=AHash_4=A，所以我们只需要将Hash2Hash_2减去Hash4×p2Hash_4\times p^2，而这时候我们又发现p2p^2中的指数与从左到右的意思相同，即需要取的长度，所以公式是：
[l,r]的Hash值=Hashl−Hashr+1×pr−l+1Hash_l-Hash_{r+1}\times p^{r-l+1}
CPP
ull get_hash2(int l,int r){
	return hs2[l]-hs2[r+1]*pw[r-l+1];
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...