Вам даны две строки \(A\) и \(B\), представляющие эссе двух учеников, которые подозреваются в мошенничестве. Для любых двух строк \(C\), \(D\) мы определяем оценку их сходства \(S(C,D)\) как \(4\cdot LCS(C,D) - |C| - |D|\), где \(LCS(C,D)\) обозначает длину наибольшей общей подпоследовательности строк \(C\) и \(D\).
Вы считаете, что могла быть скопирована только часть эссе, поэтому вас интересуют их подстроки.
Вычислите максимальную оценку сходства по всем парам подстрок. Более формально, выведите максимальное значение \(S(C, D)\), по всем парам \((C, D)\), где \(C\) — некоторая подстрока \(A\), а \(D\) — некоторая подстрока \(B\).
Если \(X\) — строка, то \(|X|\) обозначает ее длину.
Строка \(a\) является подстрокой строки \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.
Строка \(a\) является подпоследовательностью строки \(b\), если \(a\) можно получить из \(b\) путем удаления нескольких (возможно, нуля или всех) символов.
Обратите внимание на разницу между подстрокой и подпоследовательностью, так как оба термина встречаются в условии задачи.
Возможно, вам будет интересно прочитать страницу Википедии о наибольшей общей подпоследовательности.
Выходные данные
Выведите максимальное значение \(S(C, D)\), по всем парам \((C, D)\), где \(C\) — некоторая подстрока \(A\), а \(D\) — некоторая подстрока \(B\).
Примечание
В первом примере:
abb из первой строки и abab из второй строки имеют LCS равный abb.
Результат равен \(S(abb, abab) = (4 \cdot |abb|\)) - \(|abb|\) - \(|abab|\) = \(4 \cdot 3 - 3 - 4 = 5\).