字符串哈希

Rabin Karp

基于 Rabin Karp 算法的字符串子串哈希值计算

TypeScript 
export function useStrHash(s: string, b = 1337, mod = 1e9 + 7) {
    const n = s.length
    const $ = BigInt
    const bb: number[] = new Array(n + 1).fill(0)
    const h: number[] = new Array(n + 1).fill(0)
    bb[0] = 1
    for (let i = 0; i < n; i++) {
        const val = s[i].charCodeAt(0)
        bb[i + 1] = (bb[i] * b) % mod
        h[i + 1] = (h[i] * b + val) % mod
    }

    // [l, r) 包含 l 不包含 r
    return (l: number, r: number) => {
        if (h[l] * bb[r - l] > Number.MAX_SAFE_INTEGER)
            return (
                (Number($(h[r]) - (($(h[l]) * $(bb[r - l])) % $(mod))) + mod) %
                mod
            )

        return (h[r] - ((h[l] * bb[r - l]) % mod) + mod) % mod
    }
}
JavaScript 
export function useStrHash(s, b = 1337, mod = 1e9 + 7) {
    const n = s.length
    const $ = BigInt
    const bb = new Array(n + 1).fill(0)
    const h = new Array(n + 1).fill(0)
    bb[0] = 1
    for (let i = 0; i < n; i++) {
        const val = s[i].charCodeAt(0)
        bb[i + 1] = (bb[i] * b) % mod
        h[i + 1] = (h[i] * b + val) % mod
    }
    return (l, r) => {
        if (h[l] * bb[r - l] > Number.MAX_SAFE_INTEGER)
            return (
                (Number($(h[r]) - (($(h[l]) * $(bb[r - l])) % $(mod))) + mod) %
                mod
            )
        return (h[r] - ((h[l] * bb[r - l]) % mod) + mod) % mod
    }
}
Rust 
use std::ops::{Bound, RangeBounds};

pub struct StrHash {
    hash: Vec<u64>,
    pow: Vec<u64>,
}

impl StrHash {
    const MOD: u64 = 1e9 as u64 + 7;
    const BASE: u64 = 1337;

    pub fn from_str(s: &str) -> Self {
        let s = s.as_bytes();
        let n = s.len();
        let mut hash = vec![0; n + 1];
        let mut pow = vec![0; n + 1];
        pow[0] = 1;
        for i in 0..n {
            hash[i + 1] = (hash[i] * Self::BASE + s[i] as u64) % Self::MOD;
            pow[i + 1] = pow[i] * Self::BASE % Self::MOD;
        }
        Self { hash, pow }
    }

    pub fn get<R: RangeBounds<usize>>(&self, range: R) -> u64 {
        let start = match range.start_bound() {
            Bound::Included(&s) => s,
            Bound::Excluded(&s) => s + 1,
            _ => 0,
        };
        let end = match range.end_bound() {
            Bound::Included(&e) => e + 1,
            Bound::Excluded(&e) => e,
            _ => self.hash.len() - 1,
        };

        let hl = self.hash[start];
        let hr = self.hash[end];
        let pow_len = self.pow[end - start];
        (hr + Self::MOD - (hl * pow_len) % Self::MOD) % Self::MOD
    }
}
Java 

public class StringHash {

    private final long[] hash;
    private final long[] pow;
    private final int b = 1337;
    private final int mod = 1000000007;

    public StringHash(String s) {
        int n = s.length();
        hash = new long[n + 1];
        pow = new long[n + 1];
        pow[0] = 1;
        for (int i = 0; i < n; i++) {
            hash[i + 1] = (hash[i] * b + s.charAt(i)) % mod;
            pow[i + 1] = pow[i] * b % mod;
        }
    }

    public long hash(int i, int j) {
        return (hash[j] - hash[i] * pow[j - i] % mod + mod) % mod;
    }
}