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

スポンサーリンク
この記事を読んで分かること
  • ローリングハッシュとは何か

ローリングハッシュとは

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

データの一部をハッシュ化して効率的に検索するアルゴリズム

です。

 

ある文字列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)

コメント

タイトルとURLをコピーしました