Круглые слова
После недавнего конца света Азамат, наконец, выучил алгоритм нахождения наибольшей общей подпоследовательности (LCS - longest common subsequence), и ему сразу стало интересно: как будет работать алгоритм, если слова будут круглыми?
В круглых словах не имеет значения с какого символа они начинаются и в каком направлении читаются. Например, слово algorithm можно прочитать как rithmalgo и как oglamhtir.
Если для слов algorithm и grammar в обычном представлении длина наибольшей общей подпоследовательности равна 3 (слово grm), то для круглого варианта этих же слов длина наибольшей общей подпоследовательности равна 4 (слово grma).
Азамат быстро убедился, что известный алгоритм не может получить правильный ответ для круглых слов. Напишите программу, которая сделает это.
Входные данные
В двух строках задается по одному слову. Слова не пустые и длина каждого символа не более 2000 символов.
Выходные данные
Выведите одно целое число - длину наибольшей общей подпоследовательности заданных круглых слов.