Java教程

Hash数组 快速进行字符串匹配

本文主要是介绍Hash数组 快速进行字符串匹配，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

转自https://blog.csdn.net/Mikchy/article/details/103995537

 1.自然溢出法

对于自然溢出方法，我们定义 Base ，而MOD对于自然溢出方法，就是 unsigned long long 整数的自然溢出，相当于MOD 是2^6^4-1

 hash[i]=hash[i-1]*Base+idx(s[i])

 2.单Hash

定义了 Base 和 MOD，有了对应的要求余 MOD。所以一般用 long long 就可以了。

hash[i]=(hash[i-1]*Base+idx(S[i]))%MOD

3.双Hash

将一个字符串用不同的Base和MOD，hash两次，将这两个结果用一个二元组表示，作为一个总的Hash结果。
hash1[i]=(hash1[i-1]*Base1+idx*(s[i]))%MOD1

hash2[i]=(hash2[i-1]*Base2+idx*(s[i]))%MOD2

 这个方法可以很有效的避免出现冲突。 结果再用pair来存就可以了，之后比较两个二元组是否相同。

<hash1[i],hash2[i]>

求子串的Hash值

 

直接看可知S的[1,2]的子串就等于S1，所以它们对应的Hash应该相同。 所以要将之前的所有系数都消掉。

 

记得结果要取模运算

 

 

 

 

这篇关于Hash数组 快速进行字符串匹配的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航