Задача. Напишите программу, которая для каждой строки из заданного набора [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