Задача взята с сайта e-olymp.
Задача
Дана строка [latex] A = [/latex] [latex] a_1a_2…a_n [/latex] и строка [latex] B = [/latex] [latex] b_1b_2…b_m [/latex]. Также дано число [latex] L [/latex].
Нужно узнать, есть ли у строк [latex] A [/latex] и [latex] B [/latex] общая подстрока длиной [latex] L [/latex].
Входные данные
В первых двух строках записаны строки [latex]A[/latex] и [latex]B[/latex], состоящие из строчных латинских букв. Эти строки непустые и имеют длину не более [latex]100000[/latex] символов. В третьей строке записано целое число [latex]L (0 \leq L \leq 100000) [/latex] — длина общей подстроки.
Выходные данные
В выходной файл выведите [latex]YES[/latex], если существует общая подстрока такой длины. В противном случае выведите [latex]NO[/latex].
Тесты
# |
Входные данные |
Выходные данные |
1
|
saaa
baaa
3 |
YES |
2
|
raabc
taaac
3 |
NO |
3
|
aaaaaaaka
akaa
3 |
YES |
4
|
abcdfeg
qwertycdfeg
10 |
NO |
Код 1
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
|
#include <iostream> #include <map> using namespace std; struct state { int len, link; map <char,int> next; }; state st[2*100000]; int sz, last; void sa_init() { sz = 0; last = 0; st[0].len = 0; st[0].link = -1; sz++; } void sa_extend (char c) { int cur = sz++; st[cur].len = st[last].len + 1; int p; for (p = last; p != -1 && !st[p].next.count(c); p = st[p].link) st[p].next[c] = cur; if (p == -1) st[cur].link = 0; else { int q = st[p].next[c]; if (st[p].len + 1 == st[q].len) st[cur].link = q; else { int clone = sz++; st[clone].len = st[p].len + 1; st[clone].next = st[q].next; st[clone].link = st[q].link; st[q].link = st[cur].link = clone; } } last = cur; } int longest_common_string (string a, string b) { sa_init(); for (int i = 0; i < a.length(); i++) sa_extend (a[i]); int v = 0, l = 0, best = 0, bestpos = 0; for (int i = 0; i < b.length(); i++) { while (v != 0 && ! st[v].next.count(b[i])) { v = st[v].link; l = st[v].len; } if (st[v].next.count(b[i])) { v = st[v].next[b[i]]; l++; } if (l > best){ best = l; bestpos = i; } } return best; } int main() { string a, b; int n; cin >> a >> b >> n; if (longest_common_string(a, b) >= n) cout << "YES"; else cout << "NO"; return 0; } |
Решение 1
Суффиксный автомат
Создадим структуру
struct state, которая будет хранить информацию о переходах.
len — это длина строки (далее будем использовать, как длину строки в каком-то состоянии),
link — это суффиксальная ссылка, список переходов будем хранить в контейнере
map <char, int> next, где ключом будет выступать символ, а значением — номер состояния.. Сам суффиксный автомат будем хранить в массиве этой структуры. Заведем переменные
last и
sz, отвечающие за последнее состояние и номер нового состояния соответственно.
Нам потребуется функция инициализирующая суффиксный автомат
sa_init(). Так как вначале состояние лишь одно, то его длина равна [latex]0[/latex], а суффиксную ссылку приравняем к [latex]-1[/latex].
В автомат будем добавлять символы поочередно, для чего нам потребуется еще одна функция
sa_extend(). В начале которой будем присваивать новому состоянию соответствующий номер. А затем будем просматривать все переходы из последнего состояния по текущему символу. Таким образом переход либо будет, либо нет. Если его нет, то добавим его в текущее состояние
cur и продолжим смотреть дальше, если же при этом мы дошли до состояния, на которое указывает суффиксная ссылка изначального состояния (нулевого), то суффиксную ссылку текущего состояния приравняем к нулю. Далее рассматриваем случай, когда из текущего состояния по символу переход существует, обозначим
q за состояние, куда ведет переход.
Поиск наибольшей общей подстроки
Сначала для строки
a построим суффиксный автомат. Заведем две переменные, благодаря которым найдем совпадающую часть двух строк. Для этого нужна переменная, отвечающая за состояние
v и переменная, отвечающая за длину совпадающей части
l. Если есть переход, то переходим и увеличиваем длину на 1. Если нету, то уменьшаем длину совпадающей подстроки и переходим в новое состояние, меняя
l. Цикл будет работать до тех пор, пока не найдем переход. Однако, если по суффиксным ссылкам мы дошли до состояния, в которое ведет ссылка изначальной вершины, то символ не встретился. Теперь длина наибольшей общей подстроки
bestpos — это максимум из всех значений
l.
Код 2
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
|
#include <iostream> #include <cstring> using namespace std; int main() { char a[100001], b[100001]; int l1, l2, l, k = 0; cin >> a >> b >> l; l1 = strlen(a); l2 = strlen(b); if (l1 < l || l2 < l) cout << "NO"; else { for (int i = 0; i < l1; i ++) { for (int j = i; j <= l ; j ++) { if (a[j] == b[j]) k ++; else i ++; if (k == l) { cout << "YES"; return 0; } } k = 0; } cout << "NO"; } return 0; } |
Решение 2
Стоит отметить сразу, что данный код, по сути не работает на некоторых тестах, например когда символы, которые должны входить в искомую наибольшую подстроку, стоят в начале или конце обоих строк или хотя бы одной из них. Однако, как показывает практика, тесты на e-olymp данный способ посимвольного сравнения проходит. В данном варианте решения будем использовать c-string. Сами строки объявлены так:
char a[100001], b[100001];, где [latex]100001[/latex] — это максимальная длина строки, которая может быть по условию задачи, и еще [latex]+1[/latex]. Объявить можно было еще и так:
char * a = new char [100001];
Ссылки
ideone (1)
ideone (2)
e-olymp (1)
e-olymp (2)
Related Images:
Для отправки комментария необходимо войти на сайт.