No.1018 suffixsuffixsuffix

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 21
作問者 : maspymaspy / テスター : beetbeet
1 ProblemId : 4014 / 出題時の順位表
問題文最終更新日: 2020-04-03 11:13:42

問題文

長さ $N$ の文字列 $S$ と、正の整数 $M$、長さ $Q$ の数列 $K_1,\ldots,K_Q$ が与えられます。

文字列 $S$ を $M$ 回繰り返してできる文字列を $T$ とします。 $T$ の接尾辞 $T_1, T_2, \ldots, T_{NM}$ を辞書順に並べたとき、$K_1,\ldots,K_Q$ 番目の接尾辞を求めてください。

ただし、$T$ の接尾辞 $T_i$ とは、$T$ の $i$ 文字目から末尾までの部分文字列のことであるとします。

入力

$N\ M\ Q$
$S$
$K_1\ K_2\ \ldots \ K_Q$

  • $N$ は正の整数で、$1\leqq N\leqq 10^5$ を満たす。
  • $M$ は正の整数で、$1\leqq M\leqq 10^9$ を満たす。
  • $Q$ は正の整数で、$1\leqq Q\leqq \min(NM, 10^5)$ を満たす。
  • $S$ は英小文字のアルファベットからなる長さ $N$ の文字列である。
  • $K_i$ は正の整数で、$1\leqq K_1 < K_2 < \cdots < K_Q \leqq NM$ を満たす。

出力

各 $i$ に対し、$K_i$ 番目の接尾辞が $T_{n_i}$ となるような $n_i$ を求め、空白区切りで出力してください。
最後に改行してください。

サンプル

サンプル1
入力
4 2 8
puyo
1 2 3 4 5 6 7 8
出力
8 4 5 1 6 2 7 3

$T = \text{puyopuyo}$ です。接尾辞を辞書順に並べると、次の順に並びます。

  • $T_8 = \text{o}$
  • $T_4 = \text{opuyo}$
  • $T_5 = \text{puyo}$
  • $T_1 = \text{puyopuyo}$
  • $T_6 = \text{uyo}$
  • $T_2 = \text{uyopuyo}$
  • $T_7 = \text{yo}$
  • $T_3 = \text{yopuyo}$

サンプル2
入力
5 10 4
ahaha
10 20 30 40
出力
5 3 1 4

サンプル3
入力
5 10 4
ihihi
10 20 30 40
出力
7 4 11 8

サンプル4
入力
26 1000000000 1
abcdefghijklmnopqrstuvwxyz
26000000000
出力
26

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。