Strings of Eternity

题目描述

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

存在一个非负整数 $j$，使得 $i$ 个 $t$ 的连接构成的字符串是 $j$ 个 $s$ 的连接构成的字符串的一个子串。

输入格式

输入通过标准输入给出，格式如下： $s$ $t$

输出格式

如果满足下述条件的非负整数 $i$ 的个数是有限的，输出这些 $i$ 的最大值；如果个数是无限的，输出 $-1$。

abcabab
ab

3

aa
aaaaaaa

-1

aba
baaab

0

提示

$1 \leq |s| \leq 5 \times 10^5$ $1 \leq |t| \leq 5 \times 10^5$ $s$ 和 $t$ 由小写英文字母组成。字符串 $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$ 总是满足问题中的条件。$3$ 个 $t$ 的连接 $ababab$ 是 $2$ 个 $s$ 的连接 $abcabababcabab$ 的一个子串，所以 $i = 3$ 满足条件。 另一方面，$4$ 个 $t$ 的连接 $abababab$ 不是任何个数的 $s$ 的连接的子串，所以 $i = 4$ 不满足条件。 同理，任何大于 $4$ 的整数也不满足条件。因此，满足条件的非负整数 $i$ 的个数是有限的，这些 $i$ 的最大值是 $3$。
对于任意非负整数 $i$，$i$ 个 $t$ 的连接都是 $4i$ 个 $s$ 的连接的子串。因此，存在无限多个满足条件的非负整数 $i$。
如注所述，$i = 0$ 总是满足条件。

标签: AtCoder|abc135F

来源

AtCoder|abc135F