/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
英小文字のみからなる 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 を出力してください。
制約
- 1 \leq |S| \leq 5\times 10^5
- 1 \leq |T| \leq 5\times 10^5
- S,T は英小文字のみからなる文字列
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
S の接頭辞を k 個連結することで T と一致させられるような最小の正整数 k を出力せよ。 T と一致させる事が不可能な場合は -1 を出力せよ。
入力例 1
aba ababaab
出力例 1
3
T= ababaab は ab + aba + ab と書け、ab, aba はそれぞれ S= aba の接頭辞となっています。
ababaab を 2 個以下の aba の接頭辞の連結によって表す方法はないため、3 を出力します。
入力例 2
atcoder ac
出力例 2
-1
T を S の接頭辞の連結によって表す方法はないため、-1 を出力します。
Score : 600 points
Problem Statement
You are given two strings S and T consisting of lowercase English letters.
Find the minimum positive integer k such that you can choose (not necessarily distinct) k prefixes of S so that their concatenation coincides with T.
In other words, find the minimum positive integer k such that
there exists a k-tuple (a_1,a_2,\ldots, a_k) of integers between 1 and |S| such that
T=S_{a_1}+S_{a_2}+\cdots +S_{a_k},
where S_i denotes the substring of S from the 1-st through the i-th characters and + denotes the concatenation of strings.
If it is impossible to make it coincide with T, print -1 instead.
Constraints
- 1 \leq |S| \leq 5\times 10^5
- 1 \leq |T| \leq 5\times 10^5
- S and T are strings consisting of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S T
Output
Print the minimum positive integer k such that you can choose k prefixes of S so that their concatenation coincides with T. It is impossible to make it coincide with T, print -1 instead.
Sample Input 1
aba ababaab
Sample Output 1
3
T= ababaab can be written as ab + aba + ab, of which ab and aba are prefixes of S= aba.
Since it is unable to express ababaab with two or less prefixes of aba, print 3.
Sample Input 2
atcoder ac
Sample Output 2
-1
Since it is impossible to express T as a concatenation of prefixes of S, print -1.