#P18580. Insertions
Insertions
Insertions
给定三个字符串 ,用 表示字符串 的长度,其余类似。
在字符串 的位置 ()插入完整的字符串 ,会得到新字符串:先是 的前 个字符,然后是完整的 ,最后是 剩余的 个字符。
我们希望选择合适的 ,使新字符串中模式串 作为子串出现的次数尽可能多。不同出现可以重叠。
例如,将 插入 :
- 得到 ;
- 得到 ;
- 得到 。
若 ,最佳位置是 ,此时在起点 和 各有一次匹配。若 ,最佳位置是 或 ,均有一次匹配,而 时没有匹配。
输入格式
第一行字符串 ,第二行字符串 ,第三行字符串 。
- ;
- 三个字符串均只含小写英文字母。
输出格式
输出一行四个整数,以空格分隔,依次为:
- 能达到的 的最大出现次数;
- 达到该最大次数的不同插入位置 的数量;
- 这些最佳位置中的最小值;
- 这些最佳位置中的最大值。
插入位置包括 和 。如果所有位置都没有匹配,则它们仍都是最佳位置。
样例输入 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
样例说明
第一组样例对应题目描述中的第一个例子。