Description

给定三个字符串 $s$、$t$ 和 $p$。我们用竖线表示字符串的长度，例如 $|s|$ 表示 $s$ 的长度，依此类推。如果我们将 $t$ 插入到 $s$ 的第 $k$ 个位置（$0 \leq k \leq |s|$），则结果是一个新字符串：它由 $s$ 的前 $k$ 个字符、接着整个 $t$，最后是 $s$ 剩下的 $|s| - k$ 个字符组成。我们希望选择一个 $k$，使得新字符串中作为子串的 $p$ 出现次数尽可能多。

例如，将 $t = \text{aba}$ 插入 $s = \text{ab}$ 的位置 $k = 0$，得到字符串 $\text{abaab}$；插入位置 $k = 1$，得到字符串 $\text{aabab}$；插入位置 $k = 2$，得到字符串 $\text{ababa}$。如果我们关注 $p = \text{aba}$ 的出现次数，最佳插入位置是 $k = 2$，此时有两次出现：$\text{ababa}$ 和 $\text{ababa}$（如本例所示，$p$ 的出现可以重叠）。如果我们关注 $p = \text{aa}$，则最佳插入位置是 $k = 0$ 或 $k = 1$，此时 $p$ 出现一次，而 $k = 2$ 时 $p$ 出现 $0$ 次。

Input Format

第一行输入字符串 $s$，第二行输入字符串 $t$，第三行输入字符串 $p$。

Output Format

输出一行，包含四个用空格分隔的整数：

1. 经过合理选择 $k$ 后，插入 $t$ 到 $s$ 中能得到的 $p$ 作为子串的最大出现次数。
2. 能达到最大出现次数的不同 $k$ 的个数（$k$ 的取值范围为 $0, 1, \ldots, |s|$）。
3. 能达到最大出现次数的最小 $k$。
4. 能达到最大出现次数的最大 $k$。

ab
aba
aba

2 1 2 2

abaab
aba
ababa

1 3 1 5

eeoeo
eoe
eeo

2 3 1 4

Hint

说明

前三个例子与题目描述中的示例一致。

输入范围

• $1 \leq |s| \leq 10^5$
• $1 \leq |t| \leq 10^5$
• $1 \leq |p| \leq 10^5$
• 所有字符串均由小写英文字母组成。

由 ChatGPT 4.1 翻译