No.515 典型LCP

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 33
作問者 : koba-e964koba-e964 / テスター : ei1333ei1333

1 ProblemId : 1408 / 出題時の順位表

問題文

文字列からなる配列$s_1,\cdots,s_N$があります。 以下のような$M$個のクエリに答えてください:
「$1\le i < j \le N$を満たす整数$i,j$に対して、文字列$s_i,s_j$の最長共通接頭辞の長さを求めよ。」
$M$個のクエリは、シードx,dから以下の方法によって生成されます。注意深く読んで実装してください。

for k in 1 .. M
  i[k] = (x / (n - 1)) + 1
  j[k] = (x % (n - 1)) + 1
  if (i[k] > j[k])
    swap(i[k], j[k])
  else
    j[k] = j[k] + 1
  end
  x = (x + d) % (n * (n - 1))
end
ただし、計算は多倍長整数を使って行われるものとし、割り算"/"は実数としてみなした時の商の整数部分を返すものとします。

入力

$N$
$s_1$
$\vdots$
$s_N$
$M$ $x$ $d$

(2017/5/5 22:46修正: Nの最小値を1から2にしました)
$2 \le N \le 100000 = 10^5$
$|s_i| \ge 1$ for all $1 \le i \le N$
$\sum_{i} |s_i| \le 800000 = 8 \times 10^5$
各$s_i$はラテン文字の小文字('a'から'z')からなる。
$1 \le M \le 3000000 = 3 \times 10^6$
$0 \le x < N(N - 1)$
$0 \le d < N(N - 1)$
$x$,$d$は整数である。

出力

各$k$に対して、$s_{i_k}$と$s_{j_k}$の最長共通接頭辞の長さを計算して、その和を改行付きで1行に出力してください。

サンプル

サンプル1
入力
4
kinesis
koba
variance
kobushu
3 1 2
出力
4

最初のクエリにおいて、$x=1$なので$i=1, j=3$であり、"kinesis"と"variance"のLCPは""なので、長さは0です。
2個目では$x=3$なので$i=1,j=2$であり、"kinesis"と"koba"のLCPは"k"なので、長さは1です。
3個目では$x=5$なので$i=2,j=4$であり、"koba"と"kobushu"のLCPは"kob"なので、長さは3です。
最終的な出力はそれらの合計である4です。

サンプル2
入力
5
aaaaa
dadad
aaaab
abcbc
aaaac
4 1 1
出力
9

各クエリの結果は4,1,4,0なので、総和の9を出力します。

提出ページヘ