2023-11-08：用go语言，字符串哈希原理和实现 比如p = 233, 也就是课上说的选择的质数进制 “ 3 1 2 5
2023-11-08：用go语言，字符串哈希原理和实现
比如p = 233, 也就是课上说的选择的质数进制
" 3 1 2 5 6 ..."
hash[0] = 3 * p的0次方
hash[1] = 3 * p的1次方 + 1 * p的0次方
hash[2] = 3 * p的2次方 + 1 * p的1次方 + 2 * p的0次方
hash[3] = 3 * p的3次方 + 1 * p的2次方 + 2 * p的1次方 + 5 * p的0次方
hash[4] = 3 * p的4次方 + 1 * p的3次方 + 2 * p的2次方 + 5 * p的1次方 + 6 * p的0次方
次方是倒过来的，课上讲错了
所以hash[i] = hash[i-1] * p + arr[i]，这个方式就可以得到上面说的意思
于是，你想得到子串"56"的哈希值
子串"56"的哈希值 = hash[4] - hash[2]*p的2次方(就是子串"56"的长度次方)
hash[4] = 3 * p的4次方 + 1 * p的3次方 + 2 * p的2次方 + 5 * p的1次方 + 6 * p的0次方
hash[2] = 3 * p的2次方 + 1 * p的1次方 + 2 * p的0次方
hash[2] * p的2次方 = 3 * p的4次方 + 1 * p的3次方 + 2 * p的2次方
所以hash[4] - hash[2] * p的2次方 = 5 * p的1次方 + 6 * p的0次方
这样就得到子串"56"的哈希值了
抱歉，课上讲错了。应该是上面的方式。
所以，子串s[l...r]的哈希值 = hash[r] - hash[l-1] * p的(r-l+1)次方
也就是说，hash[l-1] * p的(r-l+1)次方，正好和hash[r]所代表的信息，前面对齐了
减完之后，正好就是子串s[l...r]的哈希值。
来自左程云。
答案2023-11-08：
go和c++代码用灵捷3.5编写，不需要修改。
大体过程如下：
rightCheck函数的过程：
1.检查l1和l2是否超出字符串边界，如果超出则返回false。
2.如果l1和l2相等，则直接返回true。
3.判断从l1开始长度为length的子串和从l2开始长度为length的子串是否相等，如果相等则返回true，否则返回false。
hashCheck函数的过程：
1.计算l1到r1和l2到r2两个子串的哈希值。
2.检查r1和r2是否超出字符串边界，如果超出则返回false。
3.根据哈希值判断两个子串是否相等，如果相等则返回true，否则返回false。
rightCheck函数的时间复杂度：O(length)
hashCheck函数的时间复杂度：O(1)
rightCheck函数的额外空间复杂度：O(1)
hashCheck函数的额外空间复杂度：O(1)
go完整代码如下：
package?main
import?(
"fmt"
"math/rand"
)
const?MAXN?=?100005
var?pow?[MAXN]int64
var?hash?[MAXN]int64
var?base?=?499
func?rightCheck(str?string,?l1?int,?l2?int,?length?int)?bool?{
if?l1+length?>?len(str)?||?l2+length?>?len(str)?{
return?false
}
if?l1?==?l2?{
return?true
}
return?str[l1:l1+length]?==?str[l2:l2+length]
}
func?build(str?string,?n?int)?{
pow[0]?=?1
for?j?:=?1;?j?
pow[j]?=?pow[j-1]?*?int64(base)
}
hash[0]?=?int64(str[0]-'a')?+?1
for?j?:=?1;?j?
hash[j]?=?hash[j-1]*int64(base)?+?int64(str[j]-'a')?+?1
}
}
func?hashCheck(n,?l1,?l2,?length?int)?bool?{
r1?:=?l1?+?length?-?1
r2?:=?l2?+?length?-?1
if?r1?>=?n?||?r2?>=?n?{
return?false
}
return?hashf(l1,?r1)?==?hashf(l2,?r2)
}
func?hashf(l,?r?int)?int64?{
var?ans?int64
ans?=?hash[r]
if?l?==?0?{
ans?-=?0
}?else?{
ans?-=?hash[l-1]?*?pow[r-l+1]
}
return?ans
}
func?randomString(length,?v?int)?string?{
str?:=?make([]byte,?length)
for?i?:=?0;?i?
str[i]?=?byte('a'?+?(int64(v)*int64(i))%26)
}
return?string(str)
}
func?main()?{
test?:=?"abcabcabcabcabcabcabcabc"
size?:=?len(test)
build(test,?size)
fmt.Println(hashCheck(size,?6,?15,?3))
fmt.Println("测试开始")
N?:=?10000
V?:=?3
testTeams?:=?100
testTimes?:=?5000
LEN?:=?6
for?i?:=?0;?i?
n?:=?(int)(rand.Float64()*float64(N))?+?1
str?:=?randomString(n,?V)
build(str,?n)
for?k?:=?0;?k?
l1?:=?(int)(rand.Float64()?*?float64(n))
l2?:=?(int)(rand.Float64()?*?float64(n))
length?:=?(int)(rand.Float64()*float64(LEN))?+?1
ans1?:=?rightCheck(str,?l1,?l2,?length)
ans2?:=?hashCheck(n,?l1,?l2,?length)
if?ans1?!=?ans2?{
fmt.Println("出错了!")
break
}
}
}
fmt.Println("测试结束")
}
在这里插入图片描述c++完整代码如下：
#include?
#include?
#include?
using?namespace?std;
const?int?MAXN?=?100005;
long?long?pow0[MAXN];
long?long?hashArr[MAXN];
int?base?=?499;
bool?rightCheck(string?str,?int?l1,?int?l2,?int?len)?{
if?(l1?+?len?>?str.length()?||?l2?+?len?>?str.length())?{
return?false;
}
if?(l1?==?l2)?{
return?true;
}
return?str.substr(l1,?len)?==?str.substr(l2,?len);
}
void?build(string?str,?int?n)?{
pow0[0]?=?1;
for?(int?j?=?1;?j?
pow0[j]?=?pow0[j?-?1]?*?base;
}
hashArr[0]?=?str[0]?-?'a'?+?1;
for?(int?j?=?1;?j?
hashArr[j]?=?hashArr[j?-?1]?*?base?+?str[j]?-?'a'?+?1;
}
}
bool?hashCheck(int?n,?int?l1,?int?l2,?int?len)?{
int?r1?=?l1?+?len?-?1;
int?r2?=?l2?+?len?-?1;
if?(r1?>=?n?||?r2?>=?n)?{
return?false;
}
return?hashArr[l1?+?len?-?1]?-?(l1?==?0???0?:?hashArr[l1?-?1]?*?pow0[len])?==?hashArr[l2?+?len?-?1]?-?(l2?==?0???0?:?hashArr[l2?-?1]?*?pow0[len]);
}
string?randomString(int?len,?int?v)?{
string?str;
for?(int?i?=?0;?i?
str?+=?char('a'?+?rand()?%?v);
}
return?str;
}
int?main()?{
string?test?=?"abcabcabcabcabcabcabcabc";
int?size?=?test.length();
build(test,?size);
cout?
cout?
int?N?=?10000;
int?V?=?3;
int?testTeams?=?100;
int?testTimes?=?5000;
int?LEN?=?6;
for?(int?i?=?0;?i?
int?n?=?rand()?%?N?+?1;
string?str?=?randomString(n,?V);
build(str,?n);
for?(int?k?=?0;?k?
int?l1?=?rand()?%?n;
int?l2?=?rand()?%?n;
int?len?=?rand()?%?LEN?+?1;
bool?ans1?=?rightCheck(str,?l1,?l2,?len);
bool?ans2?=?hashCheck(n,?l1,?l2,?len);
if?(ans1?!=?ans2)?{
cout?
break;
}
}
}
cout?
return?0;
}
在这里插入图片描述
- 发表于:
- 原文链接：https://page.om.qq.com/page/OxPCh-9Sv6bB7O0aJ_EHKYgA0
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
