외양간의 메아리
면접 대비시간 제한1초메모리 제한128 MB
두 소문자 문자열이 주어질 때, 한 문자열의 접두사이면서 다른 문자열의 접미사인 가장 긴 문자열의 길이를 구한다.
문제
소들은 외양간에서 "음메" 하고 우는 것을 좋아합니다. 울음소리가 메아리로 되돌아오기 때문인데, 항상 완벽하게 되돌아오지는 않습니다. 훌륭한 비서인 Bessie는 울음소리가 나갈 때와 되돌아올 때의 정확한 문자열을 기록해 두었고, 두 문자열이 얼마나 겹치는지 궁금해합니다.
두 개의 문자열이 주어집니다. 각 문자열은 a부터 z까지의 소문자로만 이루어지며, 두 문자열 길이의 합은 1 이상 80 이하입니다. 어떤 문자열이 한 문자열의 접두사이면서 동시에 다른 문자열의 접미사일 때, 이를 두 문자열의 겹침(overlap)이라고 부릅니다. 두 문자열 사이에서 가능한 가장 긴 겹침의 길이를 구하세요.
예를 들어 다음 두 울음소리를 생각해 봅시다.
moyooyoxyzooo
yzoooqyasdfljkamo
첫 번째 문자열의 끝부분 'yzooo'는 두 번째 문자열의 앞부분과 겹칩니다. 두 번째 문자열의 끝부분 'mo'는 첫 번째 문자열의 앞부분과 겹칩니다. 가장 긴 겹침은 'yzooo'이고, 그 길이는 5입니다.
입력
- 첫째 줄과 둘째 줄: 각 줄에 울음소리 또는 그 메아리에 해당하는 문자열이 하나씩 주어집니다.
출력
- 첫째 줄: 한 문자열의 앞부분과 다른 문자열의 끝부분 사이에서 가능한 가장 긴 겹침의 길이를 정수 하나로 출력합니다.
힌트
위 입력 예시에서 'abcxxxxabcx'는 첫 번째 문자열의 접두사이면서 두 번째 문자열의 접미사이며, 그 길이는 11입니다.