여기서의 “부분”은 LCS문제에서의 “부분”과는 다른 의미임을 명심하라.

nice라는 문자열이 있다면 이 문제에서의 부분문자열의 집합은

{‘’, n, i, c, e, ni, ic, ce, nic,ice, nice}

LCS문제에서의 “부분”에서는 nce도 하나의 부분문자열로 볼 수 있지만 이 문제에서는 부분문자열이 아니다. (즉, 이 문제에서의 “부분”은 원래 문자열에서 일정 부분을 잘라낸 것이다.)

photography와 autograph 두 문자열이 있다고 할 때, ph, grap, to 등의 부분문자열이 있으며, 이 중 최대의 길이를 갖는 부분문자열은 tograph이다.

입력

출력

입출력 예

입력

photography
autograph

출력 

7
tograph