e-olymp 2171. Поиск набора образцов

Задача. Напишите программу, которая для каждой строки из заданного набора [latex]S[/latex] проверяет, верно ли, что она содержит как подстроку одну из строк из набора [latex]T[/latex].

Входные данные

Первая строка содержит натуральное число [latex]n (n\leq100)[/latex] — количество строк в наборе [latex]T[/latex]. Каждая из следующих [latex]n[/latex] строк содержит непустую строку длины не более [latex]80[/latex]-ти символов.

Оставшаяся часть файла содержит строки из набора [latex]S[/latex]. Каждая строка состоит из ASCII символов с кодами от [latex]32[/latex] до [latex]126[/latex] включительно. Строка может быть пустой; гарантируется, что длины строк не превышают [latex]250[/latex]-ти символов.

Гарантируется, что размер входного файла не превышает [latex]1[/latex] Мбайт.

Выходные данные

Выведите все строки из набора [latex]S[/latex] (в том порядке, в котором они находятся во входном файле), содержащие как подстроку по крайней мере одну строку из набора [latex]T[/latex].

Задача взята с сайта e-olymp.

Тесты

Test Input Output
1 3
gr
sud
abc
lksh
sudislavl
kostroma
summer
group b
sudislavl
group b
2 4
a
b
+ +
xxx
ababa
dfs
c + +
qwerty
xxxx
ababa
c + +
xxxx
3 1
a
a
b
a
c
a
d
a
a
a
4 2
bab
aba
aabba
w w w

 
Код программы

Алгоритм

Мы последовательно перебираем все строки [latex]s[/latex] из набора [latex]S[/latex]. Для каждой из них найдем вхождение хотя бы одной строки [latex]t[/latex] из набора [latex]T[/latex]. Для этого мы воспользуемся алгоритмом Рабина-Карпа. Он заключается в следующем: мы сравниваем подстроки [latex]s[/latex] длины [latex]\left | t \right |[/latex]  со строкой [latex]t[/latex], предварительно закодировав их с помощью хеша. Если после мы перебрали все подстроки, но так и не получили равенство,  строка [latex]t[/latex] не является подстрокой  [latex]s[/latex] и мы переходим к следующему образцу.

Однако данный алгоритм не целесообразно использовать для строк единичной длины. Про большом количестве таких строк неэффективность алгоритма становится очень заметной. Поэтому мы создаем отдельный набор образцов, состоящих ровно из одного символа. Если на вход поступает строка единичной длины, мы просто ищем ее в этом наборе за [latex]O(n)[/latex].

Код программы

Засчитанное решение на сайте e-olymp.com

Related Images: