Codeforces Round 129 (Div. 1) |
---|
Закончено |
Маленький Слоник очень любит строки.
У него есть массив a из n строк, состоящих из строчных латинских букв. Пусть элементы массива пронумерованы от 1 до n, тогда элемент номер i обозначим ai. Для каждой строки ai (1 ≤ i ≤ n) Маленький Слоник хочет найти количество пар целых чисел l и r (1 ≤ l ≤ r ≤ |ai|) таких, что подстрока ai[l... r] является подстрокой как минимум k строк из массива a (включая i-ю строку).
Помогите Маленькому Слонику решить эту задачу.
Если вы не знакомы с основными обозначениями в строковых задачах, в примечании приведены соответствующие определения.
В первой строке задано два целых числа через пробел — n и k (1 ≤ n, k ≤ 105). В следующих n строках задан массив a. В i-ой строке записана непустая строка ai, состоящая из строчных латинских букв. Суммарная длина всех строк ai не превосходит 105.
В единственной строке выведите n целых чисел разделенных единичными пробелами — i-е число является ответом для строки ai.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
3 1
abc
a
ab
6 1 3
7 4
rubik
furik
abab
baba
aaabbbababa
abababababa
zero
1 0 9 9 21 30 0
Пусть задана строка a = a1a2... a|a|, тогда обозначим через |a| длину строки, а через ai — i-й символ строки.
Подстрокой a[l... r] (1 ≤ l ≤ r ≤ |a|) строки a называется строка alal + 1... ar.
Строка a является подстрокой строки b, если существует такая пара целых чисел l и r (1 ≤ l ≤ r ≤ |b|), что b[l... r] = a.
Название |
---|