J - Substring Query
Darjeeling
4
s
1024
MB
100
点
問題文
英小文字からなる文字列 $S$ が与えられます。
以下の $Q$ 個のクエリに答えてください。
各 $i=1,2,\ldots,Q$ について、$i$ 番目のクエリでは英小文字からなる文字列 $T_i$ が与えられます。$S$ の部分文字列かつ $T_i$ の部分文字列である空でない文字列のうち、最長のものの長さを出力してください。そのような文字列が存在しない場合は $0$ を出力してください。
部分文字列とは
$S$ の部分文字列とは、$S$ の先頭から $0$ 文字以上、末尾から $0$ 文字以上削除して得られる文字列のことをいいます。例えば、ab は abc の部分文字列ですが、ac は abc の部分文字列ではありません。
制約
- $1 \leq |S| \leq 2{,}000$
- $1 \leq Q \leq 200{,}000$
- $1 \leq |T _ i|$
- $\sum _ {i=1}^{Q} |T _ i| \leq 10^{6}$
- $Q$ は整数
- $S$, $T _ i$ は英小文字のみからなる
入力
入力は以下の形式で標準入力から与えられる。
$Q$
$S$
$T _ 1$
$T _ 2$
$\vdots$
$T _ Q$
出力
$Q$ 行出力せよ。$i$ 行目には、$i$ 番目のクエリに対する答えを出力せよ。
入力例 1
6
abcbd
abcd
dcba
edcba
xxabcbdxx
ac
zzz
出力例 1
3
2
2
5
1
0
$1$ 番目のクエリでは、a, bc, abc などが abcbd の部分文字列かつ abcd の部分文字列であるような空でない文字列として考えられます。これらのうち最長の文字列は abc であるため、 $3$ を出力してください。
$5$ 番目のクエリでは、 a または c が条件を満たす最長の文字列としてあてはまるので、 $1$ を出力してください。
$6$ 番目のクエリでは、条件を満たすような空でない文字列が存在しないため、 $0$ を出力してください。
入力例 2
5
vrcprocon
vrchat
program
contest
coconuts
vrccpcpc
出力例 2
3
3
3
4
3
入力例 3
9
aaaa
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaa
aaaaaaaaa
出力例 3
1
2
3
4
4
4
4
4
4