道具として使っていると忘れがちですが、ローリングハッシュには線形性があります。
ローリングハッシュ
$n$ 要素の配列 $\lbrace a_1, a_2, a_3, \cdots, a_{n}\rbrace$ のローリングハッシュ $f(\lbrace a_n\rbrace)$ を次のように定めます。
f(\lbrace a_n\rbrace)=a_1b^{n-1}+a_2b^{n-2}+\cdots+a_n \mod{M}
ただし、$b$ はローリングハッシュの基数、$M$ は見ての通り割る数です。
配列の和
$n$ 要素の 2 つの配列の和を次のように定めます。
\lbrace a_n\rbrace + \lbrace b_n\rbrace=\lbrace a_1+b_1, a_2+b_2, \cdots, a_n+b_n\rbrace
$n$ 次元ベクトルの和と同じです。
ハッシュ値の和
f(\lbrace a_n\rbrace)=a_1b^{n-1}+a_2b^{n-2}+\cdots+a_n \mod{M}
f(\lbrace b_n\rbrace)=b_1b^{n-1}+b_2b^{n-2}+\cdots+b_n \mod{M}
ですので、辺々足し合わせると次のようになります。
f(\lbrace a_n\rbrace)+f(\lbrace b_n\rbrace)=(a_1+b_1)b^{n-1}+(a_2+b_2)b^{n-2}+\cdots+a_n+b_n \mod{M}
したがって、
f(\lbrace a_n\rbrace)+f(\lbrace b_n\rbrace)=f(\lbrace a_n\rbrace +\lbrace b_n\rbrace)
このように加法性があると言えます。
応用
ローリングハッシュを再計算することなく、配列の全要素に定数を加算したときのハッシュ値を得ることができます。
おわり
斉次性はまたこんど。Mac の Safari で見ると数式がかなり歪んで見えて辛いです。