원형 단어

아자마트는 두 문자열의 최장 공통 부분수열을 얼마 전에 배웠다. 이제는 원형 단어 두 개의 최장 공통 부분수열이 궁금하다.

원형 단어는 어느 글자에서 읽기 시작하든, 어느 방향으로 읽든 모두 같은 단어로 본다. 원형 단어 algorithm은 rithmalgo로 읽어도 되고 oglamhtir로 읽어도 된다.

보통 단어로 보면 algorithm과 grammar의 최장 공통 부분수열 길이는 3이고(grm), 같은 두 단어를 원형 단어로 보면 길이가 4가 된다(grma).

원형 단어 두 개가 주어진다. 각 단어를 읽는 방법을 하나씩 골라 문자열 두 개를 만든 다음, 그 두 문자열의 최장 공통 부분수열 길이를 잰다. 읽는 방법을 고르는 모든 경우 가운데 나올 수 있는 가장 긴 길이를 구하는 프로그램을 작성하라. 두 단어를 적힌 그대로 두고 표준 알고리즘을 돌리면 이 값이 나오지 않는다.

첫째 줄과 둘째 줄에 단어가 하나씩 주어진다. 두 단어 모두 비어 있지 않고, 길이는 각각 2000자 이하다.

두 원형 단어의 최장 공통 부분수열 길이를 한 줄에 정수 하나로 출력한다.