e-olymp 4844. Поиск общей подстроки

Задача взята с сайта 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

Код

Решение

Построим суффиксный автомат по строке [latex]a[/latex]. Для каждой позиции в строке [latex]b[/latex] ищем наидлиннейшую общую подстроку [latex]a[/latex] и [latex]b[/latex], заканчивающуюся именно в этой позиции. Для этого будем поддерживать две переменные: текущее состояние [latex]v[/latex] и текущую длину [latex]l[/latex]. Эти две переменные будут описывать текущую совпадающую часть: её длину и состояние, которое соответствует ей. Изначально совпадение пустое. Будем рассматривать символ b[i];  и пересчитаем ответ для него. Если из состояния [latex]v[/latex] в автомате есть переход по символу b[i];, то мы просто совершаем этот переход и увеличиваем [latex]l[/latex] на единицу. Если же из состояния [latex]v[/latex] нет требуемого перехода, то мы должны попытаться укоротить текущую совпадающую часть, для чего надо перейти по суффиксной ссылке: v = st[v].link; . При этом текущую длину надо укоротить, но оставить максимально возможной l = st[v].len; . Если из нового состояния вновь не будет перехода по требуемому символу, то мы снова должны пройти по суффиксной ссылке и уменьшить [latex]l[/latex] , и так далее, пока не найдём переход, иначе символ b[i]; вообще не встречается в строке [latex]a[/latex], поэтому присваиваем v = 0;  и l = 0; и увеличиваем [latex]i[/latex]. Функция возвратит наибольшую общую подстроку [latex]s[/latex] двух строк, сравнив ее длину с [latex]n[/latex], выведем [latex]YES[/latex], при условии if (s.length() >= n) , [latex]NO[/latex] — в противном случае.

Ссылки

ideone

e-olymp

см. суффиксный автомат на e-maxx

4 thoughts on “e-olymp 4844. Поиск общей подстроки

  1. Все никак не могу понять:
    1) Как этот алгоритм проходит по времени? Это же $O(n\cdot l)$
    2) Как связан этот код с поиском общей подстроки? Он зачем-то сравнивает только символы в одинаковых позициях, при чем не идущие подряд. Зато тест

    он не проходит.

    Если хотите решать эту задачу по-честному, придется писать суффиксный массив. Если хотите немного «похачить», можно сделать полиномиальным хешированием строк. Но пока что решение просто неправильное, увы.

    • Спасибо за замечание, решение и вправду было неверным, однако победило несовершенство тестов на eolymp и даже попало в таблицу по скорости работы. Реализовал решение через суффиксный автомат. Однако была еще идея с заполнением двумерного массива, за столбцы и строки которого отвечали бы соответсвующие символы соответствующих строк. Заполнялся бы он нулями, где буквы не совпали, либо a[i-1][j-1]+1;, где символы совпали , но из-за того, что длина строки до [latex]100000[/latex] символов способ не сработал.

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