実装例
問題例
| # | ソース | 難易度 |
|---|
文字列の一致判定やLCPを高速に行うためのもの。
| 項目 | データ |
|---|---|
| 計算量 | 構築 $O(N)$ クエリ $O(\log N)$ |
| RollingHash<base>(s) | |
|---|---|
| 機能 | 初期化 |
| 引数 | $base$: 基数(素数が良い) $s$: 文字列 |
| unsigned get(x, y) | |
|---|---|
| 機能 | 文字列 $s$ の [$l$, $r$) のハッシュ値を得る |
| 引数 | $l, r$: 区間 |
| unsigned connect(h1, h2, h2len) | |
|---|---|
| 機能 | ハッシュを合成 |
| 引数 | $h1$: 結合元のhash値 $h2$: 結合先のhash値 $h2len$: h2の長さ |
| int LCP(b, l1, r1, l2, r2) | |
|---|---|
| 機能 | [l1, r1)と[l2, r2)のLCPを求める |
| # | ソース | 難易度 |
|---|