配点 : $600$ 点

問題文

英小文字からなる二つの文字列 $s, t$ が与えられます。次の条件を満たす非負整数 $i$ の個数が有限であるか判定し、有限である場合はそのような $i$ の最大値を求めてください。

• ある非負整数 $j$ が存在し、$t$ を $i$ 個連結して得られる文字列は、$s$ を $j$ 個連結して得られる文字列の部分文字列である。

注記

• 文字列 $a$ が文字列 $b$ の部分文字列であるとは、ある整数 $x$ $(0 \leq x \leq |b| - |a|)$ が存在して任意の整数 $y$ $(1 \leq y \leq |a|)$ に対して $a_y = b_{x+y}$ であることです。
• 任意の文字列に対し、それを $0$ 個連結して得られる文字列は空文字列であるとします。また、上記の定義より、空文字列は任意の文字列の部分文字列です。したがって、任意の二つの文字列 $s, t$ に対して $i = 0$ は問題文中の条件を満たします。

制約

• $1 \leq |s| \leq 5 \times 10^5$
• $1 \leq |t| \leq 5 \times 10^5$
• $s, t$ は英小文字からなる。

入力

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

$s$

$t$

出力

条件を満たす非負整数 $i$ の個数が有限である場合はそのような $i$ の最大値を、無限である場合は -1 を出力せよ。

abcabab
ab

3

$t$ を $3$ 個連結して得られる文字列 ababab は、$s$ を $2$ 個連結して得られる文字列 abcabababcabab の部分文字列であるため、$i = 3$ は条件を満たします。

一方で、$t$ を $4$ 個連結して得られる文字列 abababab は、$s$ を何個連結しても部分文字列として現れないため、$i = 4$ は条件を満たしません。

同様に、$5$ 以上の任意の整数も条件を満たしません。よって条件を満たす非負整数 $i$ の個数は有限で、その最大値は $3$ です。

aa
aaaaaaa

-1

任意の非負整数 $i$ に対し、$t$ を $i$ 個連結して得られる文字列は、$s$ を $4i$ 個連結して得られる文字列の部分文字列です。したがって条件を満たす非負整数 $i$ は無限に存在します。

aba
baaab

0

注記で述べたように、$i = 0$ は必ず条件を満たします。