字符串算法 - Rabin Karp（字符串哈希）

介绍

拉宾-卡普算法，也称字符串哈希，通过滑动地比较匹配串的Hash与原串相同长度的子串Hash，从而达到子串匹配的目的。

虽然存在一定的冲突概率且效率相对较低，但相对KMP算法也具备一定的优势。

拉宾-卡普算法在单模式搜索方面不如Knuth–Morris–Pratt算法、Boyer-Moore字符串搜索算法和其他较快的单模式字符串搜索算法，因为它的最坏情况行为很慢。然而，它是多模式搜索的首选算法。

本次代码编写参考自https://leetcode-cn.com/problems/longest-duplicate-substring/solution/wei-rao-li-lun-rabin-karp-er-fen-sou-suo-3c22/

代码

func strStr(haystack string, needle string) int {
    if len(needle) == 0 {
        return 0
    }

    // 使用uint64存储数据，解决hash加法过程中溢出问题
    var haystackHash uint64 = 0
    var needleHash uint64 = 0
    // 取一质数为底
    var p uint64 = 31
    // 与字符串首位对应的乘数
    var prime uint64 = 1

    // 先计算一遍needle的Hash
    for i := 0; i < len(needle); i++ {
        needleHash = needleHash * p + uint64(needle[i]-'a')
    }

    // 再计算一遍haystack的Hash，目前只需要计算到len(needle)的倒数第二位
    for i := 0; i < len(haystack) && i < len(needle) - 1; i++ {
        haystackHash = haystackHash * p + uint64(haystack[i]-'a')
        prime *= p
    }

    // 开始匹配逻辑
    for i := len(needle) - 1; i < len(haystack); i++ {
        haystackHash = haystackHash * p + uint64(haystack[i]-'a')
        // 可以匹配上
        if haystackHash == needleHash {
            return i - len(needle) + 1
        }
        // 减去首位的乘积
        haystackHash = haystackHash - uint64(haystack[i-len(needle)+1]-'a') * prime
    }

    return -1
}

介绍

代码

相关题目

28. 实现 strStr()