ローリングハッシュの線形性です。
前回: https://qiita.com/lowking/items/dae75be02d397530273b
ローリングハッシュ (再掲)
$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$ は見ての通り割る数です。
スカラ倍
f(k\lbrace a_n\rbrace)=k(a_1b^{n-1}+a_2b^{n-2}+\cdots+a_n) \mod{M}
分配すると、
f(k\lbrace a_n\rbrace)=ka_1b^{n-1}+ka_2b^{n-2}+\cdots+ka_n) \mod{M}
したがって、
f(k\lbrace a_n\rbrace)=f(\lbrace ka_n\rbrace)
このように斉次性があると言えます。
応用
ローリングハッシュを再計算することなく、配列の全要素を定数倍したときのハッシュ値を得ることができます。
おわり
前回のと合わせて線形性の証明になります。改めて書くとかなり当たり前っぽいですが、ローリングハッシュで解ける問題の範囲が広がる内容になったと思います。