実装で混乱しないように文字列は 0-indexed で考える．
文字列 $S$ に対して $S_{l,r}$ で $i\in[l,r)$ を満たす $i$ について $S_i$ を連結した部分文字列を表す． 例えば $S=\text{”acompany”}$ に対して $S_{1,5} = \text{”comp”}$ となる．
数列に対しても同様．
文字列 $S$ に対して $O(|S|)$ 時間の構築で，
クエリ $(l_1,r_1,l_2,r_2)$ : 部分文字列 $S_{l_1,r_1}$ と $S_{l_2,r_2}$ が等しいかどうかを判定
に $O(1)$ で答えることの出来るデータ構造．
ただしクエリの答えは確率的（本当は異なる文字列を等しいと判定することがある）．
まずは簡単のため文字列ではなく各要素が $[0,9]$ の数列について考える．
数列 $A$ に対して， $f(A)$ を $A$ を $10$ 進法の数値として見た場合の値とする． すなわち
$$ f(A) \coloneqq \sum_{i=0}^{|A|-1} v_i \times 10^{|A|-i-1} $$
例えば $A=[1,2,3,4,2,3]$ の場合 $f(A) = 123423$．
ここで $A=B \Leftrightarrow f(A)=f(B)$ が成り立つことに注目すると， $A_{l_1,r_1}=A_{l_2,r_2}$ が成立するか判定するためには $f(A_{l_1,r_1})=f(A_{l_2,r_2})$ が成立するか判定すればいいことがわかる．
したがって任意の $l,r$ に対して $f(A_{l,r})$ を高速に求めたい．（愚直に計算すると $\Omega(r-l)$ 時間）
ここで，以下の式が成立する
$$ f(A_{l,r}) = f(A_{0,r}) - 10^{r-l}f(A_{0,l}) $$