ネックレスから最も短く切り取る
玉 n 個を輪にして通したネックレスがある。
玉にはそれぞれ英小文字が一つ刻まれていて、ネックレスの文字列 S の i 文字目が i 番目の玉である。
輪になったネックレスなので、n 番目の玉の次にはまた 1 番目の玉が来る。
ネックレスから連続した玉をいくつか切り取って、文字列 T にある文字を T に出てくる個数以上ずつすべて手に入れたい。
切り取る玉はある玉から始まって番号が大きくなる向き（n 番目の次は 1 番目）に続く玉で、同じ玉を二度使うことはできない。
切り取る玉の数をできるだけ少なくせよ。
そのような方法がいくつもあれば、始まる玉の番号が最も小さいものを選ぶ。
始まる玉の番号と切り取る玉の数を、空白で区切って一行に出力せよ。
どう切っても無理なら -1 を出力する。
- 入力
- 一行目に S、二行目に T が与えられる。
どちらも英小文字だけからなる文字列である。
1 ≤ S の長さ n ≤ 100,000、1 ≤ T の長さ ≤ 100,000 - 出力
- 始まる玉の番号と玉の数を空白区切りで一行に、または -1
cabbad dc
6 2
ab aa
-1