Задача №114803. Скучная пара
Ильдар сидит на скучной онлайн-паре. И чтобы чем-то себя занять, он трансформирует строки. Изначально у него есть строка \(s\). Ильдар хочет получить из строки \(s\) строку \(t\) за минимальное число действий. За одно действие он может:
- Удалить из строки один символ на любой позиции.
- Добавить в строку любой символ на любую позицию. То есть в начало строки, в конец строки или между двумя соседними символами.
- Поменять символ на любой позиции на любой другой символ.
Минимальное количество таких действий, необходимых, чтобы преобразовать строку \(s\) в строку \(t\), также называют редакционным расстоянием между \(s\) и \(t\).
Еще у Ильдара есть \(n\) любимых строк \(w_i\). Рассмотрим последовательность строк, которые будут получены в процессе преобразования: \(s = x_1\), \(x_2\), ..., \(x_{m - 1}\), \(x_m = t\). Ильдар хочет, чтобы как можно больше строк \(w_i\) встречалось в множестве \(\{x_1, x_2, \dots, x_m\}\). Помогите Ильдару определить минимальное количество действий, необходимых, чтобы преобразовать \(s\) в \(t\), максимальное количество строк \(w_i\), которые могут получиться в процессе, а также сами эти строки.
В первой строке дана строка \(s\). Во второй строке дана строка \(t\).
В третьей строке дано одно целое число \(n\) (\(0 \le n \le 1\,000\)). В следующих \(n\) строках даны строки \(w_i\).
Все строки состоят из строчных английских букв, являются непустыми, их длина не превышает \(10\,000\). Суммарная длина всех строк не превышает \(10\,000\). Все строки являются различными. В том числе \(s \neq t\), \(s \neq w_i\) и \(t \neq w_i\).
В первой строке выведите два целых числа — минимальное количество действий, необходимых, чтобы преобразовать строку \(s\) в строку \(t\) и максимальное количество различных строк \(w_i\), которое можно получить в процессе преобразования.
Далее выведите строки \(w_i\), которые можно получить в процессе преобразования, в том порядке, в котором они будут получены. Если оптимальных ответов несколько, можно вывести любой из них.
cat dog 4 dot pot rat oat
3 1 dot
longlong double 3 doublon longleng dongle
6 2 longleng dongle