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