题目描述

英小文字のみからなる $2$ つの文字列 $S,T$ が与えられます。

(相異なっても良い) $S$ の接頭辞を $k$ 個連結することで $T$ と一致させられるような最小の正整数 $k$ を求めてください。

すなわち、$S$ の $1$ 文字目から $i$ 文字目までを取り出した文字列を $S_i$ としたときに、 $k$ 個の $1$ 以上 $|S|$ 以下の整数の組 $(a_1,a_2,\ldots,\ a_k)$ によって、
$T=S_{a_1}+S_{a_2}+\cdots\ +S_{a_k}$（ここで $+$ は文字列としての連結を表す）と書くことができるような 最小の正整数 $k$ を求めてください。

$T$ と一致させる事が不可能な場合は $-1$ を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$S$ $T$

输出格式

$S$ の接頭辞を $k$ 個連結することで $T$ と一致させられるような最小の正整数 $k$ を出力せよ。 $T$ と一致させる事が不可能な場合は $-1$ を出力せよ。

题目大意

给定仅存在小写英文字母的字符串 $S, T$。你需要将 $T$ 分割成 $k$ 个 $S$ 的前缀（或着说用 $S$ 的若干个前缀组成 $T$），最小化 $k$，输出最小值。若 $k$ 不存在输出 -1。

aba
ababaab

3

atcoder
ac

-1

提示

制約

• $1\ \leq\ |S|\ \leq\ 5\times\ 10^5$
• $1\ \leq\ |T|\ \leq\ 5\times\ 10^5$
• $S,T$ は英小文字のみからなる文字列

Sample Explanation 1

$T=$ ababaab は ab + aba + ab と書け、ab, aba はそれぞれ $S=$ aba の接頭辞となっています。 ababaab を $2$ 個以下の aba の接頭辞の連結によって表す方法はないため、$3$ を出力します。

Sample Explanation 2

$T$ を $S$ の接頭辞の連結によって表す方法はないため、$-1$ を出力します。