[Java] BOJ 5582번 공통 부분 문자열

5582번: 공통 부분 문자열

---

풀이

DP를 사용하여 해결했습니다. 

문제에서 나온 1번 예시를 풀어보면

ABRACA~ 를 S1이라 하고 인덱스는 i, ECADA~ 를 S2라 하고 인덱스는 j라고 한다면 S1[i] == S2[j]라면 이전까지 연속되는 부분 문자열에 새로 공통된 문자가 들어가므로 S1과 S2에 공통되는 이전 문자인 memo[i -1][j - 1]에 저장된 길이에 + 1을 하여 즉, memo[i -1][j - 1] + 1을 현재 위치에서 공통되는 연속된 부분 문자열인 memo[i][j] 갱신하면 됩니다. 이때, S1[i]!= S2[j] 일 경우는 연속되는 부분 문자열을 찾는 것이므로 0으로 채워주면 됩니다.

그리고 최대 길이를 찾으면 되므로 최대 길이를 갱신하면 됩니다.

	(공백)	A	B	R	A	C	A	D	A	B	R	A
(공백)	0	0	0	0	0	0	0	0	0	0	0	0
E	0	0	0	0	0	0	0	0	0	0	0	0
C	0	0	0	0	0	1	0	0	0	0	0	0
A	0	1	0	0	1	0	2	0	1	0	0	1
D	0	0	0	0	0	0	0	3	0	0	0	0
A	0	1	0	0	1	0	1	0	4	0	0	1
D	0	0	0	0	0	0	0	2	0	0	0	0
A	0	1	0	0	1	0	1	0	3	0	0	1
B	0	0	2	0	0	0	0	0	0	4	0	0
R	0	0	0	3	0	0	0	0	0	0	5	0
B	0	0	1	0	0	0	0	0	0	1	0	0
C	0	0	0	0	0	1	0	0	0	0	0	0
R	0	0	0	1	0	0	0	0	0	0	1	0
D	0	0	0	0	0	0	0	1	0	0	0	0
A	0	1	0	0	1	0	1	0	2	0	0	1
R	0	0	0	1	0	0	0	0	0	0	1	0
A	0	1	0	0	2	0	1	0	1	0	0	2

 

---

코드

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

public class Main {
	public static int answer;
	public static String S1, S2;
	public static int[][] memo;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		S1 = br.readLine();
		S2 = br.readLine();
		
		memo = new int[S2.length() + 1][S1.length() + 1];
		
		for (int i = 0; i < S2.length(); ++i) {
			for (int j = 0; j < S1.length(); ++j) {				
				if (S2.charAt(i) == S1.charAt(j)) {
					memo[i + 1][j + 1] = memo[i][j] + 1;
					answer = (answer < memo[i + 1][j + 1]) ? memo[i + 1][j + 1] : answer;
				}
			}
		}
		
		System.out.println(answer);
	}
}

---

pyo7410/Algorithm