Матрица сравнения для двух строк $$$s$$$ и $$$t$$$ над алфавитом $$$\{A, C, G, T\}$$$ определяется следующим образом. Рассмотрим операцию: вставка в строку символа «-». Такой символ можно вставить в начало и конец строки, а также между любой парой имеющихся символов в строке. Вставим произвольное (возможно, нулевое) количество таких символов в $$$s$$$ и $$$t$$$ так, чтобы их длины стали равны. Затем запишем полученные строки в матрицу друг под другом. Например, для строк ACT и AGTT одна из возможных матриц сравнения выглядит так: $$$$$$ \begin{matrix} A & C & - & T\\ A & G & T & T \end{matrix} $$$$$$

Вес такой матрицы считается как сумма весов каждого столбца. Вес столбца определяется следующим образом: если символы в столбце совпадают и оба не равны «-», то вес равен $$$+1$$$, и $$$-1$$$ в противном случае. Не допускаются матрицы, в котором в одном и том же столбце находятся два символа «-». Например, вес матрицы, приведенной выше, равен $$$+1 -1 -1 +1 = 0$$$. Наибольший возможный вес матрицы сравнения для двух строк называется их схожестью.

Подстрокой строки $$$s = s_i, \ldots, s_{|s|}$$$ является строка $$$s_{i j} = s_i, \ldots, s_j, \, 1 \leq i \leq j \leq |s|$$$; подстрока не может быть пустой. Для данных двух строк $$$s$$$ и $$$t$$$ найдите подстроки $$$s'$$$ в строке $$$s$$$ и $$$t'$$$ в $$$t$$$ такие, что схожесть $$$s'$$$ и $$$t'$$$ максимальная среди всех подстрок $$$s$$$ и $$$t$$$.