https://www.acmicpc.net/problem/9251

---

LCS

LCS는 Longest Common Subsequence의 약자로 최장 공통 부분 수열이라고 한다.

부분 문자열(substring)과 차이는 substring은 연속된 부분 문자열이고, subsequence는 연속적이지 않은 부분 문자열이다.

풀이

---

두 문자열에서 일치하는 수열의 길이를 구해야는데 보통 DP로 풀이한다.

예제로 주어진 ACAYKP 와 CAPCAK가 있다.

둘 중 하나를 기준으로 잡고 남은 하나는 기준과 비교를 한다.

두 번째 문자열의 첫 단어인 C는 AC와 비교했을 때 C는 AC의 부분 수열이 된다.

이어 CA는 마찬가지로 ACA와 비교한다면 CA는 ACA의 부분 수열이 되기 시작한다.

이처럼 알파벳을 하나씩 증가시키면서 이전의 순서에서 구한 값을 참고로 값이 변한다.

최종적으로 다음과 같은 결과를 얻을 수 있다.

표를 보면 문자가 서로 같은 경우 이전까지의 lcs 길이에 1을 더하는 것을 확인할 수 있다. 그런데 여기서 이전까지의 lcs 길이는 현재 위치에서 대각선 위이다.

반대로 문자가 서로 같지 않은 경우 비교한 문자가 포함되어 있는 직전 lcs 길이, 즉 표에서 위와 왼쪽 값 중 큰 값이 오게 된다.

최종적으로 점화식은 다음과 같다.

str1[i] == str2[j] -> lcs[i][j] = lcs[i-1][j-1]+1
str1[i] != str2[j] -> max(lcs[i][j-1], lcs[i-1][j-1])

코드

'''java
import java.io.*;

public class Main {
static int[] dx = {0, 0, -1, 1};
static int[] dy = {1, -1, 0, 0};
static boolean[][] visit;
static int n, m;
static int ans = 0;
static int[] chess;

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    char[] s1 = br.readLine().toCharArray();
    char[] s2 = br.readLine().toCharArray();
    int n = s1.length;
    int m = s2.length;
    int[][] lcs = new int[m + 1][n + 1];
    char[] str1 = new char[n + 1];
    char[] str2 = new char[m + 1];

    str1[0] = 0;
    str2[0] = 0;
    for (int i = 1; i <= n; i++) {
        str1[i] = s1[i - 1];
    }
    for (int i = 1; i <= m; i++) {
        str2[i] = s2[i - 1];
    }

    for (int i = 1; i < lcs.length; i++) {
        for (int j = 1; j < lcs[i].length; j++) {
            if (str2[i] == str1[j]) {
                lcs[i][j] = lcs[i - 1][j - 1] + 1;
            } else
                lcs[i][j] = Math.max(lcs[i][j - 1], lcs[i - 1][j]);
        }
    }
    //printLcs(lcs);
    int ans = 0;
    for (int i = 1; i < lcs.length; i++) {
        for (int j = 1; j < lcs[i].length; j++)
            ans = Math.max(ans, lcs[i][j]);
    }

    bw.write(ans + "\n");
    br.close();
    bw.close();
}

private static void printLcs(int[][] lcs) {
    for (int i = 0; i < lcs.length; i++) {
        for (int j = 0; j < lcs[i].length; j++)
            System.out.print(lcs[i][j] + " ");
        System.out.println();
    }
}

}
'''