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

ローリングハッシュとは

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

ある文字列sの中に文字列wordが含まれているかを判断する時などに利用するアルゴリズムとなります。

s = hotdog ,word = dogの場合、hotdogの中にdogという文字列があります。

hotdog
     dog

まずはwordの文字列をハッシュ化します。

hash("dog")
# -4048568721914396232

sの文字列を3文字ずつハッシュ化して、wordの文字列と一致するか確認します。

hash("hot") # -43685858351830637
hash("otd") # -4595107538059492567
hash("tdo") # 7757932126173094536
hash("dog") # -4048568721914396232

参考文献

文字列ハッシュ – 競合プログラミングのアルゴリズム (cp-algorithms.com)