ei1333's page

ローリングハッシュ(Rolling-Hash)

説明

文字列の一致判定やLCPをハッシュを使って高速に求めるもの。

計算量

• RollingHash: $O(N)$
• get, connect: $O(1)$
• LCP: $O(\log N)$

実装例

問題例