永恒字符串

题目描述

给定两个由小写英文字母组成的字符串 $s, t$。判断满足以下条件的非负整数 $i$ 的个数是否有限,如果有限,求出这样的 $i$ 的最大值。

• 存在某个非负整数 $j$,使得把 $t$ 连接 $i$ 个得到的字符串,是把 $s$ 连接 $j$ 个得到的字符串的子串。

提示

• 字符串 $a$ 是字符串 $b$ 的子串,是指存在某个整数 $x$ ($0 \le x \le |b| - |a|$),使得对任意整数 $y$ ($1 \le y \le |a|$) 都有 $a_y = b_{x+y}$。

• 对任意字符串,把它连接 $0$ 个得到的字符串是空字符串。另外,根据上述定义,空字符串是任意字符串的子串。因此,对任意两个字符串 $s, t$,$i = 0$ 都满足题目描述中的条件。

输入格式

输入按以下格式从标准输入给出:

$s$
$t$

输出格式

如果满足条件的非负整数 $i$ 的个数有限,则输出这样的 $i$ 的最大值;如果无限,则输出 -1。

样例

abcabab
ab

3

把 $t$ 连接 $3$ 个得到的字符串 ababab 是把 $s$ 连接 $2$ 个得到的字符串 abcabababcabab 的子串,因此 $i = 3$ 满足条件。

另一方面,把 $t$ 连接 $4$ 个得到的字符串 abababab 无论把 $s$ 连接多少个都不会作为子串出现,因此 $i = 4$ 不满足条件。

同理,任意大于等于 $5$ 的整数也不满足条件。因此满足条件的非负整数 $i$ 的个数有限,其最大值是 $3$。

aa
aaaaaaa

-1

对任意非负整数 $i$,把 $t$ 连接 $i$ 个得到的字符串都是把 $s$ 连接 $4i$ 个得到的字符串的子串。因此满足条件的非负整数 $i$ 有无限多个。

aba
baaab

0

如提示中所述,$i = 0$ 必定满足条件。

数据范围

• $1 \le |s| \le 5 \times 10^5$
• $1 \le |t| \le 5 \times 10^5$
• $s, t$ 由小写英文字母组成