2082. Неточный поиск

Задача поиска заданной подстроки в тексте имеет неоспоримое значение и ее решение реализовано в большинстве языков программирования в виде функциональности стандартной библиотеки. Однако, зачастую необходимо решать задачу неточного поиска. Назовем расстоянием между двумя строками a и b наименьшее количество операций, необходимое для того, чтобы строку a перевести в строку b. Разрешенные операции: замена любого символа любым другим, вставка любого символа в произвольную позицию в строке и удаление произвольного символа. Например, расстояние между строками "кот" и "конь" равно 2. Ваша задача в заданном тексте найти подстроку, которая имеет расстояние до заданной не более d.

Вход. В первой строке записана строка, в которой следует осуществлять поиск. Длина строки не менее 1 символа и не более 2·10⁶. Далее содержится строка, содержащая образец поиска. Его длина не менее 1 символа и не более 50 символов. Заданные строки содержат строчные и прописные буквы латинского алфавита и цифры. Последняя строка содержит целое число d (0 ≤ d ≤ 50) – наибольшее расстояние между образцом поиска и искомой подстрокой.

Выход. Выведите два целых числа start, length, где start – позиция первого символа найденной подстроки, а length – ее длина. Нумерация символов в строке начинается с нуля. Если решений несколько, выведите любое.

Пример входа 1

thisisthetesttext
tester
2
 

Пример выхода 1

9 4

Пример входа 2

thesecondsampletestforproblemaboutthestrings
pattern
4
 

Пример выхода 2

12 5

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

Если строку a можно перевести в строку b совершив k операций, то для преобразования b в a также достаточно k операций.

Обозначим через s₁ строку, в которой производится поиск, а через s₂ строку образец. Объявим массив m[length(s₁)][length(s₂)], в котором m[i][j] равно наименьшему расстоянию между подстрокой, оканчивающейся в позиции i и j-ым префиксом образца. Считаем, что первая буква в строке находится в первой позиции.

Сначала положим m[i][0] = 0: расстояние между пустой строкой образца и подстрокой, оканчивающейся в позиции i, равно нулю. Все остальные значения m[i][j] изначально положим равными плюс бесконечности.

Рассмотрим переходы из ячейки m[i][j]:

m[i + 1][j + 1] = m[i][j], если s₁[i + 1] = s₂[j + 1].

m[i + 1][j + 1] = m[i][j] + 1, если s₁[i + 1] ≠ s₂[j + 1]. Стоимость изменения одного символа s₁[i + 1] на s₂[j + 1] равно единице.

m[i + 1][j] = m[i][j] + 1. Соответствует удалению (i + 1)-го символа из первой строки.

m[i][j + 1] = m[i][j] + 1. Соответствует удалению (j + 1)-го символа из второй строки.

Если после заполнения массива m для некоторого i выполняется неравенство m[i][length(s₂)] ≤ d, то ответ найден, искомая подстрока заканчивается в позиции i.

Для нахождения позиции начала подстроки следует завести массив len, в котором len[i][j] равно длине подстроки, соответствующей значению m[i][j].

Пример

Пусть s₁ = ddaa, s₂ = iad, d = 2.

m[i][j]	j = 0	j = 1 i	j = 2 a	j = 3 d
i = 0	0	1	2	3
d i = 1	0	1	2	2
d i = 2	0	1	2	2
a i = 3	0	1	1	2
a i = 4	0	1	1	2

Наименьшим i, для которого неравенство m[i][3] ≤ 2 имеет место, будет i = 1. Равенство m[1][3] = 2 означает, что расстояние между d и iad равно 2. Ответом будет пара чисел 0 1.

len[i][j]	j = 0	j = 1 i	j = 2 a	j = 3 d
i = 0	0	0	0	0
d i = 1	0	1	1	1
d i = 2	0	1	2	2
a i = 3	0	1	2	2
a i = 4	0	1	2	3

Например, равенство m[3][3] = 2 означает, что существует подстрока, заканчивающаяся в позиции 3, которую можно получить из iad двумя преобразованиями. len[3][3] = 2 говорит о том, что длина такой подстроки равна 2. Следовательно искомой подстрокой будет da: сначала следует удалить из iad букву d, после чего в ia букву i заменить на d.

Рассмотрим еще один пример, в котором s₁ = abca, s₂ = abc, d = 0.

m[i][j]	j = 0	j = 1 a	j = 2 b	j = 3 c
i = 0	0	1	2	3
a i = 1	0	0	1	2
b i = 2	0	1	0	1
c i = 3	0	1	1	0
a i = 4	0	0	1	1

len[i][j]	j = 0	j = 1 a	j = 2 b	j = 3 c
i = 0	0	0	0	0
a i = 1	0	1	1	1
b i = 2	0	1	2	2
c i = 3	0	1	3	3
a i = 4	0	1	1	4

Ответом будет пара чисел 0 3.