• 개인 공부 목적으로 작성한 포스팅입니다.
  • 아래 출처를 참고하여 작성하였습니다. :)

문자열과 부분수열의 차이점

lcs

LC Substring

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

  • 연속한 값만 취급합니다.

점화식

if i == 0 or j == 0:  # margin 셋팅
	LCS[i][j] = 0
elif string_A[i] == string_B[j]:
	LCS[i][j] = LCS[i - 1][j - 1] + 1
else:
	LCS[i][j] = 0

예시 코드

  • 중요한 건, 실제 사용하는 점화식은 LCS[i][j] = LCS[i-1][j-1] + 1 하나입니다.
public static void main(String[] args) throws IOException {
    String str1 = br.readLine();
    String str2 = br.readLine();

    int len1 = str1.length();
    int len2 = str2.length();

    dp = new int[len1+1][len2+1];
    int ans = 0;

    for (int i = 1; i <= len1; ++i) {
        for (int j = 1; j <= len2; ++j) {
            char c1 = str1.charAt(i-1);
            char c2 = str2.charAt(j-1);

            if (c1 == c2) {
                dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1] + 1);
                ans = Math.max(ans, dp[i][j]);
            }
        }
    }
}

LC Subsequence

공통 부분 수열(Longest Common Substring)

  • 연속하지 않아도 됩니다.

점화식

if i == 0 or j == 0:  # margin 셋팅
	LCS[i][j] = 0
elif string_A[i] == string_B[j]:
	LCS[i][j] = LCS[i - 1][j - 1] + 1
else:
	LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])

예시 코드

public static void main(String[] args) throws IOException {
    String str1 = br.readLine();
    String str2 = br.readLine();

    int len1 = str1.length();
    int len2 = str2.length();

    dp = new int[len1 + 1][len2 + 1];
    int ans = 0;

    for (int i = 1; i <= len1; ++i) {
        for (int j = 1; j <= len2; ++j) {
            char c1 = str1.charAt(i-1);
            char c2 = str2.charAt(j-1);

            if (c1 == c2) {
                dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1] + 1);
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }

            ans = Math.max(ans,dp[i][j]);
        }
    }

}

dp[i][j] 이전 단계

  • 중요한 건, 최장 공통 부분 수열에서 dp 현재 단계인 dp[i][j]의 이전 단계는 3가지입니다.
  • dp[i][j], dp[i-1][j], dp[i][j-1]
    • 이 3가지 중에 max 값을 취하는 것입니다.
    • 이 중에서 dp[][] 값을 증가 시킬 수 있는 경우는, str[i]와 str2[j] 값이 같아 '모두 한 칸 증가할 수 있을 때' 입니다.