[알고리즘] LCS(Longest Common Subsequence, Substring) 알고리즘 - JAVA / 자바

최장 공통부분 수열과 최장 공통부분 문자열의 차이점

12346789	▶	134679	Longest Common Subsequence(수열)
13465798		346	Longest Common Substring(문자열)

---

최장 공통부분 수열(Longest Common Subsequence)

 : 부분 수열이 서로 붙어있을 필요 없이 앞뒤 순서만 따져 길이가 최대가 되는 부분 수열을 찾는 알고리즘

// LCS 수열 최대 길이 구하기
if(str1.charAt(i) == str2.charAt(j))
	LCS[i][j] = LCS[i-1][j-1] + 1;
else
	LCS[i][j] = Math.max(LCS[i-1][j], LCS[i][j-1]);

 Java 코드 

// LCS 수열 길이 구하기
for(int i=1; i<=s1.length(); i++)
	for(int j=1; j<=s2.length(); j++) {
		if(s1.charAt(i-1) == s2.charAt(j-1))
			lcs[i][j] = lcs[i-1][j-1] + 1;
		else
			lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);
	}
// 앞전에 구한 LCS 수열 출력
int r = s1.length(), c = s2.length();
bw.write(lcs[r][c]+"\n");
Stack<Character> stack = new Stack<>();
while(lcs[r][c] != 0) {
	while(lcs[r][c] == lcs[r-1][c])
		r--;
	while(lcs[r][c] == lcs[r][c-1])
		c--;
	stack.add(s1.charAt(--r));
	c--;
}
while(!stack.isEmpty())
	bw.write(stack.pop());

---

최장 공통부분 문자열(Longest Common Substring)

 : 서로 붙어있는 길이가 최대인 부분 문자열을 찾는 알고리즘

// LCS 문자열 최대 길이 구하기
if(str1.charAt(i) == str2.charAt(j))
	LCS[i][j] = LCS[i-1][j-1] + 1;
else
	LCS[i][j] = 0;

 Java 코드