AT_abc135_f [ABC135F] Strings of Eternity

题目描述

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

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

输入格式

输入以以下格式从标准输入读入。

$s$ $t$

输出格式

如果满足条件的非负整数 $i$ 的个数有限，则输出满足条件的 $i$ 的最大值；如果有无穷多个满足条件的 $i$，则输出 $-1$。

样例 1

输入

abcabab
ab

输出

3

样例 2

输入

aa
aaaaaaa

输出

-1

样例 3

输入

aba
baaab

输出

0

说明/提示

注释

• 若字符串 $a$ 是字符串 $b$ 的子串，意味着存在整数 $x$（$0 \leq x \leq |b| - |a|$），对于任意整数 $y$（$1 \leq y \leq |a|$），都有 $a_y = b_{x+y}$。
• 对于任意字符串，将其连接 $0$ 次得到的字符串视为空字符串。根据上述定义，空字符串是任意字符串的子串。因此，对于任意两个字符串 $s$ 和 $t$，$i = 0$ 一定满足题目中的条件。

约束

• $1 \leq |s| \leq 5 \times 10^5$
• $1 \leq |t| \leq 5 \times 10^5$
• $s$ 和 $t$ 均由小写英文字母组成。

样例解释 1

将 $t$ 连续连接 $3$ 次得到的字符串 ababab，是将 $s$ 连续连接 $2$ 次得到的字符串 abcabababcabab 的子串，因此 $i = 3$ 满足条件。而将 $t$ 连续连接 $4$ 次得到的字符串 abababab，无论将 $s$ 连接多少次，都不会作为其子串出现，因此 $i = 4$ 不满足条件。同理，任意大于等于 $5$ 的整数也不满足条件。因此，满足条件的非负整数 $i$ 的个数是有限的，其最大值为 $3$。

样例解释 2

对于任意非负整数 $i$，将 $t$ 连续连接 $i$ 次得到的字符串，都是将 $s$ 连续连接 $4i$ 次得到的字符串的子串。因此，满足条件的非负整数 $i$ 有无穷多个。

样例解释 3

如注释所述，$i = 0$ 一定满足条件。

由 ChatGPT 4.1 翻译