yukicoder No.515 典型LCP
この記事は、yukicoder No.515 典型LCP の解説です。
遅い解法だが、C++で実装した場合、実行時間制限には間に合う。
ローリングハッシュを使ったいくつかの解法がチャレンジケースで落ちたらしいが、Trie を使えば同様のことがローリングハッシュよりは高速にできる。
生配列で Trie を作る。int Trie[800001][26];
( vector<vector<int>> でもよいが生配列のほうが速い)
今までに作った頂点数を覚えておいて、初めて見る接頭辞が来た時に頂点を増設するようなイメージでやる。
各文字列に対して Trie を辿った頂点番号の列を覚えておく。これを \(d\) とする。
サンプル \(1\) に対しては \(d\) の値は次のようになる。
- \(d_1=(0,1,2,3,4,5,6,7)\)
- \(d_2=(0,1,8,9,10)\)
- \(d_3=(0,11,12,13,14,15,16,17,18)\)
- \(d_4=(0,1,8,9,19,20,21,22)\)
\(2\) つの文字列 \(s_i,s_j\) が長さ \(k\) 以上の共通接頭辞をもつとき(に限り)、\(d_{i,k}=d_{j,k}\)( \(k\) は \(0\) -indexed)となるので二分探索ができる。
クエリの回数が \(M \le 3 \times 10^6\) と非常に多いので、
for k in 1 .. M
略
x = (x + d) % (n * (n - 1))
を
nn = n * (n - 1)
x %= nn
d %= nn
for k in 1 .. M
略
x += d
if x >= nn:
x -= nn
にするだけで 200 ms ぐらい速くなる。
実装列 #427272