Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

ローリングハッシュ題材にした問題

ローリングハッシュとは?

蟻本上級のテク。決してエロい名前ではない。

文字列S(長さn)の中に文字列T(長さm)が存在するかを愚直に調べると、O(nm)かかる。これをO(n)程度にしたい。

そこで、文字列に対するハッシュ値を使うことにする。衝突は、諦める。競プロの範疇においては、衝突しなくすることが出来るということだと理解した。

これをローリングハッシュという。b,h(互いに素)を用意して、ハッシュ値を、sum(ci * b^{m-i}) % hで定義する。こうすると、mの領域を右に一つシフトした時のハッシュ値は、前に計算した値を利用してO(1)で計算することが出来る。(b倍して差分を調整するだけ)

こうすることで、O(n)でS内のあらゆるオフセットから長さm区間についてのハッシュ値を計算することが出来る。ローリングというのは、このシフトが醸し出すローリング感から来たものだろうと推察する。

あとは、Tのハッシュ値も同様に計算すれば、その値を探せば良いことになる。

2次元拡張は出来ないのだろうか?

実装

RollingHashRawという名前になっているのは、実際に使う時は、ローリングハッシュを1つだけでは衝突確率が十分に低くならないため、b,hの違ういくつかのローリングハッシュを組み合わせて総意によって決めるようにするからである。ここでは本質的な部分だけコードを載せた。

struct RollingHashRaw {
    hash: Vec<usize>,
    m: usize, // len(t)
    b: usize,
    h: usize,
    b_pow: Vec<usize>, // b^0 .., b^m
}
impl RollingHashRaw {
    fn calc_hash(s: &[usize], m: usize, b_pow: &[usize], h: usize) -> usize {
        let mut res = 0;
        for i in 0..m {
            res += s[i] * b_pow[m-1-i];
            res %= h;
        } 
        res
    }
    fn new(s: &[usize], m: usize, b: usize, h: usize) -> RollingHashRaw {
        let n = s.len();
        assert_eq!(gcd(b, h), 1);
        assert!(n>=m);
        let mut b_pow = vec![1];
        let mut acc = 1;
        for _ in 1..m+1 {
            acc *= b;
            acc %= h;
            b_pow.push(acc);
        }
        let mut hash = vec![];
        let mut cur_hash = Self::calc_hash(&s, m, &b_pow, h);
        hash.push(cur_hash);
        for i in 1..n+1-m {
            let k = i-1;
            cur_hash *= b;
            cur_hash %= h;
            cur_hash -= s[k] * b_pow[m];
            cur_hash %= h;
            cur_hash += s[k+m];
            cur_hash %= h;
            hash.push(cur_hash);
        }
        RollingHashRaw {
            hash: hash,
            m: m,
            b: b,
            h: h,
            b_pow: b_pow,
        }
    }
    fn find(&self, t: &[usize], from: usize) -> Option<usize> {
        let th = Self::calc_hash(t, t.len(), &self.b_pow, self.h);
        let mut res = None;
        for k in from..self.hash.len() {
            if self.hash[k] == th {
                res = Some(k);
                break;
            }
        }
        res
    }
}

追記

このように概念そのものを実装してしまうと、各mについて事前計算する必要が出てしまい、場合によってはMLEする。

よってもっと発展させて、ハッシュ値をBITのような感じで計算出来るようにするのが、ライブラリとしてはより望ましいことがわかった。 参考: ローリングハッシュ - odan’s diary

問題例

F - Strings of Eternity