← 返回题目列表

AtCoder · abc135_f

F. 永恒之弦

中文机器翻译题面 查看原题

分数: 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 始终满足条件。