No.958 たぷりすたべる (回文)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 26
作問者 : treeonetreeone / テスター : TaprisちゃんTaprisちゃん
0 ProblemId : 3600 / 出題時の順位表
問題文最終更新日: 2019-12-20 22:11:48

問題文

長さ $N$ の文字列 $S$ と整数 $K$ が与えられます.

$S$ を $K$ 個連結して得られる文字列を $T$ とします.

$Q$ 個の以下のクエリが与えられるので処理してください.

  • $T$ の $A_i$ 番目の文字を中心位置とする極大回文の長さを求めてください.

補足:

$1\leq i\leq r$ に対して $T[x - i] = T[x + i]$ が成り立ち ( ただし,$1\leq x - r \leq x + r\leq KN$ ) ,

$T[x - r - 1] \ne T[x + r + 1]$ または $x - r = 1$ または $x + r = KN$ が成り立つとき,

$T[x - r..x + r]$ を $T$ の $x$ 番目の文字を中心位置とする極大回文といい,その長さは $2r + 1$ である.

入力

$N\ K\ Q$
$S$
$A_1$
$A_2$
$:$
$A_Q$
  • $S$ は英小文字からなる文字列
  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq K \leq 10^9$
  • $1 \leq Q \leq 2\times 10^5$
  • $1 \leq A_i \leq KN$
  • $N, K, Q, A_i$ は整数

出力

各クエリに対し,答えを 1 行に出力してください。

サンプル

サンプル1
入力
17 2 2
ushitapunichiakun
17
34
出力
3
1

$T$ の $17$ 番目の文字を中心位置とする極大回文は以下の下線部分で,長さは 3 です.

$T =$ ushitapunichiakunushitapunichiakun

サンプル2
入力
13 3 3
abcdefgfedcba
7
20
33
出力
13
39
13

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