题目描述

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

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

输入格式

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

$s$ $t$

输出格式

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

题目大意

给两个字符串$s$和$t$，记符号$str * x$表示字符串$str$重复$x$次。 定义一个正整数$k$合法，当且仅当满足：存在一个正整数 $j$ ，使得$t* k$是 $s* j$ 的子串 找到最大的合法正整数 $k$，或者判断可以取到无穷大。 |?|,|?|≤500,000

abcabab
ab

3

aa
aaaaaaa

-1

aba
baaab

0

提示

注記

• 文字列 $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$ は英小文字からなる。

Sample Explanation 1

$t$ を $3$ 個連結して得られる文字列 ababab は、$s$ を $2$ 個連結して得られる文字列 abcabababcabab の部分文字列であるため、$i\ =\ 3$ は条件を満たします。 一方で、$t$ を $4$ 個連結して得られる文字列 abababab は、$s$ を何個連結しても部分文字列として現れないため、$i\ =\ 4$ は条件を満たしません。 同様に、$5$ 以上の任意の整数も条件を満たしません。よって条件を満たす非負整数 $i$ の個数は有限で、その最大値は $3$ です。

Sample Explanation 2

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

Sample Explanation 3

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