LCS (Longest Common Subsequence)

[WonYong-Jang]

최장 공통 부분 수열 (LCS)

• substring 은 연속된 부분 문자열
• subsequence 은 연속적이지 않은 부분 문자열!! 구분할 것!

LCS 구하기

DP를 이용하여 특정 범위까지의 값을 구하고 다른 범위까지의 값을 구할때 이전에 구해 둔 값을 이용하여 해결

주의 : LCS는 substring을 구하는 것과 다르게 연속적이지 않아도 되기 때문에 같은 길이의 다른해가 나타날 수 있다!

LCS 출력

소스코드

for(int i=1; i<= N; i++) // base case
{
	sn[i] = s.charAt(i-1);
	L[i][0] = 0;
}
for(int i=1; i<= M; i++) // base case 
{
	tm[i] = t.charAt(i-1);
	L[0][i] = 0;
}
for(int i=1; i<= N; i++)
{
	for(int j=1; j<= M; j++)
	{
		if(sn[i] == tm[j]) // 같다면 
		{
			L[i][j] = L[i-1][j-1] + 1;
		}
		else // 다르다면 둘중 큰값으로 
		{
			L[i][j] = max(L[i-1][j], L[i][j-1]);
		}
	}
}
System.out.println(L[N][M]);

전체 소스코드 ( lcs 문자열 출력 함수 포함)

public class baek9252 {

	static int N, M;
	static char[] sn = new char[4005];
	static char[] tm = new char[4005];
	static String s, t, result;
	static int[][] L = new int[4005][4005]; // LCS 길이 
	static int[][] S = new int[4005][4005]; // LCS 문자 추적하기 위한 배열  
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		s = t = "";
		s = br.readLine();
		t = br.readLine();
		result = "";
		
		N = s.length();
		M = t.length();
		
		for(int i=1; i<= N; i++) // base case
		{
			sn[i] = s.charAt(i-1);
			L[i][0] = 0;
		}
		for(int i=1; i<= M; i++) // base case 
		{
			tm[i] = t.charAt(i-1);
			L[0][i] = 0;
		}
		for(int i=1; i<= N; i++)
		{
			for(int j=1; j<= M; j++)
			{
				if(sn[i] == tm[j]) 
				{
					L[i][j] = L[i-1][j-1] + 1;
					S[i][j] = 0;
				}
				else
				{
					L[i][j] = max(L[i-1][j], L[i][j-1]);
					if(L[i][j] == L[i][j-1]) { // 왼쪽에서 왔다면 1로 체킹 
						S[i][j] = 1;
					}
					else { // 오른쪽에서 왔다면 2로 체킹 
						S[i][j] = 2;
					}
				}
			}
		}
		solve(N, M);
		System.out.println(L[N][M]);
		System.out.println(result);
		
	}
	public static void solve(int dx, int dy)
	{
		if(!isRange(dx, dy)) return;
		
		if(S[dx][dy] == 0)
		{
			solve(dx-1,dy-1);
			result += sn[dx];
		}
		else if(S[dx][dy] == 1) solve(dx,dy-1);
		else if(S[dx][dy] == 2) solve(dx-1, dy);
	}

참고 링크 : http://twinw.tistory.com/126