두 문자열의 가장 긴 공통 부분 문자열
다이아몬드 V의견: 0
두 문자열 \(S\)와 \(T\)가 주어진다. \(S\)의 어떤 연속한 부분 문자열이면서 동시에 \(T\)의 연속한 부분 문자열이기도 한 문자열 중, 길이가 가장 긴 것의 길이를 구하여라.
예를 들어 \(S = \texttt{abcde}\), \(T = \texttt{cdebc}\)라면 공통 부분 문자열 중 가장 긴 것은 \(\texttt{cde}\)로 길이가 \(3\)이다. 공통 부분 문자열이 하나도 없으면 \(0\)을 출력한다.
두 문자열의 길이가 매우 크므로 모든 부분 문자열을 비교하는 풀이는 통과할 수 없다.
\(1 \le |S|, |T| \le 500{,}000\)
첫째 줄에 문자열 \(S\)가 주어진다.
둘째 줄에 문자열 \(T\)가 주어진다.
두 문자열은 모두 소문자 알파벳으로만 이루어져 있다.
가장 긴 공통 부분 문자열의 길이를 한 줄에 출력한다.
abcde
cdebc
3\(S=\texttt{abcde}\), \(T=\texttt{cdebc}\). 공통 부분 문자열 중 가장 긴 것은 \(\texttt{cde}\)이며 길이는 3이다.
abc
xyz
0\(\texttt{abc}\)와 \(\texttt{xyz}\)는 공통된 글자조차 없으므로 답은 0이다.
riseoj 작성
출처 Original
평가 및 의견
두 문자열의 가장 긴 공통 부분 문자열
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
두 문자열의 가장 긴 공통 부분 문자열