ローリングハッシュとは
ローリングハッシュとは、
です。
ある文字列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
コメント