分数: 600 点
问题陈述
给你两个字符串 S 和 T 由小写英文字母组成。
求最小正整数 k 这样你就可以选择(不一定不同) k 的前缀 S 使它们的串联与 T.
换句话说,找到最小的正整数 k 这样
存在一个 k-元组 (a_1,a_2,\ldots, a_k) 之间的整数 1 和 |S| 这样
T=S_{a_1}+S_{a_2}+\cdots +S_{a_k},
哪里 S_i 表示子串 S 来自 1-st 通过 i第一个字符和 + 表示字符串的串联。
如果无法使其与 T,打印 -1 。
约束
- 1 \leq |S| \leq 5\times 10^5
- 1 \leq |T| \leq 5\times 10^5
- S 和 T 是由小写英文字母组成的字符串。
输入
输入由标准输入按以下格式给出:
S T
输出
打印最小正整数 k 这样你就可以选择 k 的前缀 S 使它们的串联与 T。 让它重合是不可能的 T,打印 -1 。
示例输入 1
aba ababaab
示例输出 1
3
T= ababaab 可以写成 ab + aba + ab,其中 ab 和 aba 是前缀 S= aba.
既然无法表达 ababaab 具有两个或更少的前缀 aba,打印 3.
示例输入 2
atcoder ac
示例输出 2
-1
既然无法表达 T 作为前缀的串联 S,打印 -1.