F - 極小部分列
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
文字列 S と Q 個のクエリが与えらます。
i 番目のクエリでは文字列 T_i が与えられるので、T_i を部分列として含むような S の極小な部分文字列のうち最も左にあるものを求めてください。
ただし文字列 s が極小であるとは、s の部分文字列であって T_i を部分列として含むような s より短いものが存在しないことを指すものとします。
制約
- 1≦|S|≦10^5
- 1≦Q≦10^5
- 1≦|T_i|
- |T_i| の和は 10^5 を越えない
- S, T_i は小文字アルファベットのみからなる
入力
入力は以下の形式で標準入力から与えられる。
S Q T_1 T_2 : T_Q
出力
i 番目のクエリの答えの文字列が S の l 文字目から r 文字目までの部分文字列であるとき、i 行目に l,r を空白区切りで出力せよ。ただし、S が T_i を部分列として含まない場合は代わりに -1
を i 行目に出力せよ。
入力例 1
aaxbab 12 ab da subsequence aaxbab a aa aaa aaaa ba x xb xb
出力例 1
2 4 -1 -1 1 6 1 1 1 2 1 5 -1 4 5 3 3 3 4 3 4
1 番目のクエリについて説明します。
答えは 2 文字目から 4 文字目までの部分文字列 axb
となります。
他にも 5 文字目から 6 文字目までの部分文字列 ab
も T_1 を部分列として含む極小な部分文字列ですが、axb
の方が左にあるためこちらは答えとはなりません。
また、aaxb
は極小ではありません。
なぜなら axb
という T_i を部分列として含むような部分文字列を含むためです。