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

Код 1

Решение 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

Решение 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)

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

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

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

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

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

  2. У меня зашел такой код

    Что-то можете сказать по этому поводу?

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