Задача. Напишите программу, которая для каждой строки из заданного набора [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 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
#include <bits/stdc++.h> using namespace std; #define in_range(x,y,z) for (int x=y; x<z; x++) typedef long long ll; int find_subctr(string t, string s) { const int p = 97; // основание системы счисления для хеширования строк // вычисляем степени числа P, чтобы ускорить процесс хеширования vector<ll> p_pow (s.length()); p_pow[0] = 1; for (size_t i=1; i<p_pow.size(); ++i) p_pow[i] = p_pow[i-1] * p; // вычисляем хеши всех префиксов строки S vector<ll> h (s.length()); for (size_t i=0; i<s.length(); ++i) { h[i] = (s[i] - 't' + 1) * p_pow[i]; if (i) h[i] += h[i-1]; } // посчитаем хеш строки Т ll h_t = 0; for (size_t i=0; i<t.length(); ++i) h_t += (t[i] - 't' + 1) * p_pow[i]; // сравниваем хеши строки T и подстрок S длины |T| for (size_t i = 0; i + t.length() - 1 < s.length(); ++i) { ll cur_h = h[i+t.length()-1]; if (i) cur_h -= h[i-1]; // если равенство выполняется хотя бы один раз, мы прекращаем поиск if (cur_h == h_t * p_pow[i]) return int(i); } return -1; } int main() { vector<string>T,S,C; // наборы строк T и S, а также набор образцов единичной длины C int n; cin >> n; string tmp; getline(cin,tmp); in_range(i,0,n) { getline(cin,tmp); if(tmp.length()==1) C.push_back(tmp); T.push_back(tmp); } while(getline(cin,tmp)) { S.push_back(tmp); } in_range(i,0,S.size()) { string s=S[i]; if(s=="") continue; // отсекаем случай пустой строки if(s.length()==1) // в случае строки единичной длины ищем вхождения образцов из С простым перебором { in_range(j,0,C.size()) { string c=C[j]; if(s==c) { cout << s << "\n"; break; } } continue; } in_range(j,0,n) // во всех остальных случаях ищем вхождения строк из Т, используя алгоритм Рабина-Карпа { string t=T[j]; int pos = find_subctr(t,s); if(pos>=0) { cout << s << "\n"; break; } } } return 0; } |
Алгоритм
Мы последовательно перебираем все строки [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
Зачел, хотя решение получилось довольно громоздким и очень медленным.
Но работает. Но медленно.
Конечно, резервы оптимизации скорости у Вас есть, но, на мой взгляд лучше использовать алгоритмы типа Ахо-Корасика в которых по множеству шаблонов строится некоторая общая решающая структура. Алгоритм Ахо-Корасика хорошо (и с кодом описан) на Хабре.
Я бы посоветовал скомпоновать решение самостоятельно. Только учтите, что Ахо-Карасик находит все вхождения шаблонов в строку. Вам так много ненужно. Если найдено вхождение хоть одной строки, считаем задачу решенной.