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;

}

在这里插入图片描述