MemSQL Start[c]UP 2.0 - Round 1 |
---|
Закончено |
Заданы три строки (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).
abc
bc
cbc
3 1
abacaba
abac
abcd
11 2 0 0
Рассмотрим строку t = t1t2... t|t|, где ti обозначает i-й символ строки, а |t| обозначает длину строки t.
Подстрокой t[i... j] (1 ≤ i ≤ j ≤ |t|) будем называть строку titi + 1... tj.
Название |
---|