P13812 [CERC 2022] Insertions

给定三个字符串 $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$ 次。

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

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

### 说明 前三个例子与题目描述中的示例一致。 ### 输入范围 - $1 \leq |s| \leq 10^5$ - $1 \leq |t| \leq 10^5$ - $1 \leq |p| \leq 10^5$ - 所有字符串均由小写英文字母组成。 由 ChatGPT 4.1 翻译