No.515 典型LCP
タグ : / 解いたユーザー数 76
作問者 :
koba-e964
/ テスター :
ei1333333
問題文
文字列からなる配列$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を出力します。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。