← 返回题目列表

Codeforces · 452/E

E. 三弦

中文机器翻译题面 查看原题

给你三个字符串(s1、s2、s3)。对于每个整数 l (1 ≤ l ≤ min(|s1|, |s2|, |s3|),您需要找出存在多少个三元组 (i1, i2, i3),使得三个字符串 sk[ik... ik + l - 1] (k = 1, 2, 3) 成对相等。打印所有找到的数字模 1000000007 (109 + 7)。

如果您不确定声明中使用的某些术语,请参阅注释。

输入

前三行包含三个非空输入字符串。所有字符串的长度之和不超过3·105。所有字符串仅由小写英文字母组成。

输出

您需要输出以空格分隔的 min(|s1|, |s2|, |s3|) 个数字 — 问题的答案以 1000000007 为模(109 + 7)。

示例

输入 #1

abc
bc
cbc

输出 #1

3 1

输入 #2

abacaba
abac
abcd

输出 #2

11 2 0 0

注意

考虑一个字符串 t = t1t2... t|t|,其中 ti 表示字符串的第 i 个字符,|t| 表示该字符串的第 i 个字符。表示字符串的长度。

则 t[i... j] (1 ≤ i ≤ j ≤ |t|) 表示字符串 titi + 1... tj (t 从位置 i 到位置 j 的子串)。