공통 부분 문자열

면접 대비

시간 제한2초메모리 제한256 MB

요약

길이가 최대 4000인 두 대문자 문자열이 주어질 때, 양쪽에 연속으로 나타나는 가장 긴 부분 문자열의 길이를 구한다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 문자열, 슬라이딩 윈도우, 이분 탐색
정답자: 아직 제출이 없습니다

문제

두 문자열이 주어졌을 때, 두 문자열에 모두 연속으로 나타나는 가장 긴 공통 부분 문자열의 길이를 구하는 프로그램을 작성하시오.

문자열 $s$ 의 부분 문자열 $t$ 란 $s$ 안에서 연속으로 등장하는 문자열을 뜻한다. 예를 들어 문자열 ABRACADABRA의 부분 문자열로는 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이 있다. 반면 ABRC, RAA, BA, K는 부분 문자열이 아니다.

두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열에는 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 가운데 가장 긴 공통 부분 문자열은 ADABR이고 길이는 5이다. 한편 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 공통 부분 문자열이 빈 문자열뿐이므로 답은 0이다.

입력

첫째 줄과 둘째 줄에 각각 문자열이 하나씩 주어진다. 두 문자열은 모두 알파벳 대문자로만 이루어지며, 길이는 각각 1 이상 4000 이하이다.

출력

첫째 줄에 두 문자열에 모두 포함되는 부분 문자열 중 가장 긴 것의 길이를 출력한다. 공통 부분 문자열이 빈 문자열뿐이면 0을 출력한다.

예제2

예제 1
입력
```
ABRACADABRA
ECADADABRBCRDARA
```
예상 출력
```
5
```
예제 2
입력
```
UPWJCIRUCAXIIRGL
SBQNYBSBZDFNEV
```
예상 출력
```
0
```