LCS - Longest Common Subsequence

LCS -> 최장 공통 부분 수열/문자열 이라고 한다.

약간의 차이는 있으나 사실상 원리는 같다.

 

www.youtube.com/watch?v=P-mMvhfJhu8&feature=youtu.be

해결하는 알고리즘이다.

 

 

DP를 활용한 방식으로, 이중배열로 해결하게 되며,

원리는 2개의 문자열을,

 

각각 부분문자열을 만들어서,

동시에 하나씩 char를 추가하면서,

이전 값(부분문자열에 대한 LCS)을 비교하면서 구해나가는 방식이다.

 

예를 들어, 

 

ASDASD 라는 문자열과

ABDABD 라는 문자열의 LCS를 구해본다면,

 

1) 맨 처음 A와 A를 비교 (제일 작은 부분문자열) >> 값은 1

 

2) AS와 A & AB와 A를 비교 >> 똑같이 1(하지만 값이 달라질 수 있음) 

>> 그래서 AS AB의 값은 더 둘 중 큰 값으로 한다.

>> 왜냐면 "최대" 공통을 찾는 것이기에..

 

	A	AB
A	1	1
AS	1	1

 

 

ASD, ABD의 값의 경우 D로 공통으로 같으니까, AS / AB 비교할 때의 최대 값에서 +1을 해주면 되는 된다.

	A	AB	ABD
A	1	1	1
AS	1	1	1
ASD	1	1	2 (> (AB, AS) + 1)

 

이것을 코딩으로 생각해보면

 

이중배열을 만들고, 그 배열의 값은

>> dp[i][j] > i번째까지의 문자열과 j번째까지의 문자열의 LCS값을 나타낸다.

 

dp[i][j]의 값은 만약

1) string[i] == string[j] 의 값이 같다면, (위에서 ABD / ASD를 비교할 때)

각 문자열에 해당 동일한 문자열을 추가하기 전의 상태 dp[i-1][j-1]에 +1 을 하면 되고,

 

2) string[i] == string[j] 의 값이 같지 않다면, (위에서 AB / AS를 비교할 때)

dp[i-1][j]와 dp[i][j-1] 값 중 큰 것을 고르면 된다.

 

 

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

public class Q9251 {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String firstWord = br.readLine();
		String secondWord = br.readLine();
		
		
		//set dataTable
		int[][] table = new int[firstWord.length()+1][secondWord.length()+1];
		int max = 0;
			
		for (int i = 1; i<firstWord.length()+1; i ++) {
			for (int j = 1; j<secondWord.length()+1; j ++) {
				
				if(firstWord.charAt(i-1) == secondWord.charAt(j-1)) {
					table[i][j] = table[i-1][j-1]+1;
					if(max < table[i][j]) {
						max = table[i][j];
					}
				}
				else {
					table[i][j] = Math.max(table[i-1][j], table[i][j-1]);
				}
				
				
			}
			
		}
		
		System.out.println(max);

	}

}