programmer life guidance 101

www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256 MB 7874 3235 2482 43.407% 문제 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADA..

Longest Common Subsequence 최장 공통 부분 수열 여기서 substring은 연속된 부분 문자열이고, subsequence는 연속적이지 않은 부분 수열이다. 예로, "iamstudent" 라는 문자열에서 연속된 부분 문자열 mstu은 substring이 되고 연속적으로 이어지지는 않지만 순서는 맞는 mtue는 subsequence가 된다. 그렇다면 공통 부분 수열이란, 두 문자열이 공통으로 가지고 있는 부분 수열이다. 에를 들어 "CDABE" 와 "CDEGT"가 있다면 공통부분 수열은 {}, {C}, {D}, {E}, {C, D}, {D, E}, {C, E}, {C, D, E} 일 것이다. 최장 공통 부분 수열이란 공통 부분 수열 중에서 길이가 가장 긴 부분 수열을 뜻한다. 대표적으로..