[ABC135F] Strings of Eternity

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

[problemUrl]: https://atcoder.jp/contests/abc135/tasks/abc135_f 英小文字からなる二つの文字列 $ s,\ t $ が与えられます。次の条件を満たす非負整数 $ i $ の個数が有限であるか判定し、有限である場合はそのような $ i $ の最大値を求めてください。 - ある非負整数 $ j $ が存在し、$ t $ を $ i $ 個連結して得られる文字列は、$ s $ を $ j $ 個連結して得られる文字列の部分文字列である。

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

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

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 $ は必ず条件を満たします。