[백준] 5582 - 공통 부분 문자열

[문제링크]

5582번: 공통 부분 문자열

 

0. 두 문자열에 공통으로 등장하는, 가장 길고 연속적인 문자열(LCS) 찾기 (DP)

 

1. 두 문자열의 각 index i, j 번 문자가 동일했다면 해당 지점의 LCS 길이는?

• 각 문자열의 i-1, j-1번 까지의 LCS + 1이다

 

2. 예시) abcd 와 bcd의 경우 각 4, 3번째 문자 d가 겹친다

• 이때 LCS 길이는 abc와 bc 두 문자열의 LCS 길이 + 1이다
• abc와 bc는 c가 겹치므로 ab와 b의 LCS + 1,
• ab와 b는 b가 겹치므로 a와 ""의 LCS + 1이다
• a와 ""의 LCS는 0이므로 ab와 b는 1, abc와 bc는 2, abcd와 bcd는 3의 LCS를 가진다
• 다음에 abcde와 bcde를 계산할 때 위 결과를 활용해 3+1 = 4를 얻을 수 있다 <- DP

 

3. DP로 모든 경우에 대해 LCS를 계산하며, 가장 긴 max값만 저장 후 출력한다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		char[] fst = br.readLine().toCharArray();
		char[] snd = br.readLine().toCharArray();
		int[][]map = new int[fst.length+1][snd.length+1];
		int max=0;
		for (int i = 1; i < fst.length+1; i++) {
			for (int j = 1; j < snd.length+1; j++) {
				if(snd[j-1]==fst[i-1]) {
					map[i][j]=map[i-1][j-1]+1;
					max = Math.max(max, map[i][j]);
				}
			}
		}
		System.out.println(max);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면