分数: 600 点
问题陈述
给定两个字符串 s 和 t 由小写英文字母组成。判断是否有非负整数的个数 i 满足以下条件是有限的,并找到这样的最大值 i 如果数量有限。
- 存在一个非负整数 j 这样的串联 i 副本 t 是串联的子字符串 j 副本 s.
注释
-
一个字符串 a 是另一个字符串的子字符串 b 当且仅当存在一个整数 x (0 \leq x \leq |b| - |a|) 这样,对于任何 y (1 \leq y \leq |a|), a_y = b_{x+y} 成立。
-
我们假设任何字符串的零副本的串联都是空字符串。从上面的定义来看,空字符串是任何字符串的子字符串。因此,对于任意两个字符串 s 和 t, i = 0 满足问题陈述中的条件。
约束
- 1 \leq |s| \leq 5 \times 10^5
- 1 \leq |t| \leq 5 \times 10^5
- s 和 t 由小写英文字母组成。
输入
输入由标准输入按以下格式给出:
s t
输出
如果非负整数的个数 i 满足以下条件是有限的,打印这样的最大值 i;如果数字是无限的,则打印 -1.
示例输入 1
abcabab ab
示例输出 1
3
三个副本的串联 t, ababab,是两个副本串联的子字符串 s, abcabababcabab,所以 i = 3 满足条件。
另一方面,四个副本的串联 t, abababab,不是任意数量的副本串联的子字符串 s,所以 i = 4 不满足条件。
类似地,任何大于 4 也不满足条件。因此,非负整数的数量 i 满足条件是有限的,这样的最大值 i is 3.
示例输入 2
aa aaaaaaa
示例输出 2
-1
对于任何非负整数 i,串联 i 副本 t 是串联的子字符串 4i 副本 s。因此,非负整数有无穷多个 i 满足条件。
示例输入 3
aba baaab
示例输出 3
0
如注释中所述, i = 0 始终满足条件。