• 2023-11-08:用go语言,字符串哈希原理和实现 比如p = 233, 也就是课上说的选择的质数进制 “ 3 1 2 5 6 ...“ 0 1 2 3 4 hash[0] = 3 * p的0


    2023-11-08:用go语言,字符串哈希原理和实现

    比如p = 233, 也就是课上说的选择的质数进制

    " 3 1 2 5 6 ..."

    0 1 2 3 4

    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 < n; j++ {
    		pow[j] = pow[j-1] * int64(base)
    	}
    	hash[0] = int64(str[0]-'a') + 1
    	for j := 1; j < n; 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 < length; 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 < testTeams; i++ {
    		n := (int)(rand.Float64()*float64(N)) + 1
    		str := randomString(n, V)
    		build(str, n)
    		for k := 0; k <= testTimes; 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 < n; j++) {
            pow0[j] = pow0[j - 1] * base;
        }
    
        hashArr[0] = str[0] - 'a' + 1;
        for (int j = 1; j < n; 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 < len; i++) {
            str += char('a' + rand() % v);
        }
        return str;
    }
    
    int main() {
        string test = "abcabcabcabcabcabcabcabc";
        int size = test.length();
        build(test, size);
        cout << hashCheck(size, 6, 15, 3) << endl;
    
        cout << "测试开始" << endl;
        int N = 10000;
        int V = 3;
        int testTeams = 100;
        int testTimes = 5000;
        int LEN = 6;
        for (int i = 0; i < testTeams; i++) {
            int n = rand() % N + 1;
            string str = randomString(n, V);
            build(str, n);
            for (int k = 0; k <= testTimes; 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 << "出错了!" << endl;
                    break;
                }
            }
        }
        cout << "测试结束" << endl;
    
        return 0;
    }
    
    

    在这里插入图片描述

  • 相关阅读:
    分享自研实现的多数据源(支持同DB不同表、跨DB表、内存数据、外部系统数据等)分页查询工具类实现原理及使用
    【C语言】C的编译过程&&预处理
    R语言ggHoriPlot包绘制地平线图
    Cloud微服务:Ribbon负载均衡
    SpringBoot整合SpringSecurity [超详细] (二)获取用户信息
    git 将本地已有的一个项目上传到新建的git仓库的方法
    Java毕业设计-药品管理系统
    飞桨EasyDL实操范例:工业零件划痕自动识别
    Spring Boot 整合 Redis,使用 RedisTemplate 客户端
    【2022.12.06】备战春招Day1——每日一题 + 49.字母异位词分组
  • 原文地址:https://www.cnblogs.com/moonfdd/p/17818201.html