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:

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

  1. Зачел, хотя решение получилось довольно громоздким и очень медленным.
    Но работает. Но медленно.
    Конечно, резервы оптимизации скорости у Вас есть, но, на мой взгляд лучше использовать алгоритмы типа Ахо-Корасика в которых по множеству шаблонов строится некоторая общая решающая структура. Алгоритм Ахо-Корасика хорошо (и с кодом описан) на Хабре.
    Я бы посоветовал скомпоновать решение самостоятельно. Только учтите, что Ахо-Карасик находит все вхождения шаблонов в строку. Вам так много ненужно. Если найдено вхождение хоть одной строки, считаем задачу решенной.

Добавить комментарий