#P18580. Insertions

Insertions

Insertions

给定三个字符串 s,t,ps,t,p,用 ∣s∣|s| 表示字符串 ss 的长度,其余类似。

在字符串 ss 的位置 kk(0≤k≤∣s∣0\le k\le|s|)插入完整的字符串 tt,会得到新字符串:先是 ss 的前 kk 个字符,然后是完整的 tt,最后是 ss 剩余的 ∣s∣−k|s|-k 个字符。

我们希望选择合适的 kk,使新字符串中模式串 pp 作为子串出现的次数尽可能多。不同出现可以重叠。

例如,将 t=abat=\texttt{aba} 插入 s=abs=\texttt{ab}:

  • k=0k=0 得到 abaab\texttt{abaab};
  • k=1k=1 得到 aabab\texttt{aabab};
  • k=2k=2 得到 ababa\texttt{ababa}。

若 p=abap=\texttt{aba},最佳位置是 k=2k=2,此时在起点 00 和 22 各有一次匹配。若 p=aap=\texttt{aa},最佳位置是 k=0k=0 或 11,均有一次匹配,而 k=2k=2 时没有匹配。

输入格式

第一行字符串 ss,第二行字符串 tt,第三行字符串 pp。

  • 1≤∣s∣,∣t∣,∣p∣≤1051\le|s|,|t|,|p|\le10^5;
  • 三个字符串均只含小写英文字母。

输出格式

输出一行四个整数,以空格分隔,依次为:

  1. 能达到的 pp 的最大出现次数;
  2. 达到该最大次数的不同插入位置 kk 的数量;
  3. 这些最佳位置中的最小值;
  4. 这些最佳位置中的最大值。

插入位置包括 00 和 ∣s∣|s|。如果所有位置都没有匹配,则它们仍都是最佳位置。

样例输入 1

ab
aba
aba

样例输出 1

2 1 2 2

样例输入 2

abaab
aba
ababa

样例输出 2

1 3 1 5

样例输入 3

eeoeo
eoe
eeo

样例输出 3

2 3 1 4

样例说明

第一组样例对应题目描述中的第一个例子。