37.50.48

%20 の ブログ

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