joi 2018- 공통부분문자열[longest common substring] > 문제은행 : 정보올림피아드&알고리즘

공지   새로운 정올 베타버전이 공개되었습니다.    자세히보기


4377 : 공통부분문자열[longest common substring]

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
60 회   
시도횟수
107 회   

문제

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.

어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 

예를 들어, 문자열 ABRACADABRA의 부분 문자열은 

ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 

하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.

 

두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 

CA, CADA, ADABR, 빈 문자열 등이 있다. 

이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다.

 

만약, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 

가장 긴 공통 부분 문자열은 빈 문자열이다.​


입력형식

첫째 줄과 둘째 줄에 문자열이 주어진다. 

문자열은 대문자로 구성되어 있으며, 길이는 1 이상 4000 이하이다.​ 


출력형식

첫째 줄에 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 출력한다. 


입력 예

복사하기

ABRACADABRA
ECADADABRBCRDARA

출력 예

복사하기

5

입력 예

복사하기

UPWJCIRUCAXIIRGL
SBQNYBSBZDFNEV

출력 예

복사하기


출처

joi 2018

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP