CF452E.Three strings

You are given three strings (_s_1, _s_2, _s_3). For each integer l (1 ≤ l ≤ min(|_s_1|, |_s_2|, |_s_3|) you need to find how many triples (_i_1, _i_2, _i_3) exist such that three strings s__k[i__k... i__k + l - 1] (k = 1, 2, 3) are pairwise equal. Print all found numbers modulo 1000000007 (109 + 7).

See notes if you are not sure about some of the denotions used in the statement.

给你三个字符串 $s_1$、$s_2$、$s_3$。对于每个整数 $l$（满足 $1 \le l \le \min(|s_1|, |s_2|, |s_3|)$），你需要计算满足如下条件的三元组 $(i_1, i_2, i_3)$ 的个数：三个子串 $s_k[i_k \dots i_k + l - 1]$（其中 $k = 1, 2, 3$）两两相等。将所有求得的数值对 $1000000007$（即 $10^9 + 7$）取模后输出。

若你对题目中使用的某些符号含义不确定，请参阅题末注释。

First three lines contain three non-empty input strings. The sum of lengths of all strings is no more than 3·105. All strings consist only of lowercase English letters.

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

You need to output min(|_s_1|, |_s_2|, |_s_3|) numbers separated by spaces — answers for the problem modulo 1000000007 (109 + 7).

你需要输出 $\min(|s_1|, |s_2|, |s_3|)$ 个用空格分隔的数——即该问题的答案对 $1000000007$（$10^9 + 7$）取模的结果。

Consider a string t = _t_1_t_2... t|t|, where t__i denotes the i-th character of the string, and |t| denotes the length of the string.

Then t[i... j] (1 ≤ i ≤ j ≤ |t|) represents the string t__i__t__i + 1... t__j (substring of t from position i to position j inclusive).

考虑一个字符串 $t = t_1 t_2 \dots t_{|t|}$，其中 $t_i$ 表示字符串的第 $i$ 个字符，$|t|$ 表示字符串的长度。

那么 $t[i \dots j]$（其中 $1 \le i \le j \le |t|$）表示字符串 $t_i t_{i+1} \dots t_j$（即字符串 $t$ 中从位置 $i$ 到位置 $j$（含端点）的子串）。