AT_abc257_g [ABC257G] Prefix Concatenation

[problemUrl]: https://atcoder.jp/contests/abc257/tasks/abc257_g 英小文字のみからなる $ 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 $ を出力せよ。

### 制約 - $ 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 $ を出力します。