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

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

주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제

 

복잡도

이 문제는 임의의 수의 수열의 경우 NP-난해의 복잡도를 갖는다. 그러나 주어진 수열의 개수가 일정할 때 이 문제는 동적 계획법에 의해 다항 시간 안에 풀린다.

 

문제 이해

APPLE, APOLLO 이 두 문자열의 최장 공통 부분 문자열을 구해보자

격자를 채워보자

1. 첫줄 A에 같은 곳은 더하기 1을 해준다. 같지 않다면 앞칸의 숫자를 가지고 온다.

2. 다음 줄을 계산한다. 같지 않으면 위칸이나 왼쪽칸 중 큰값을 적는다.

같으면 왼쪽위(대각선)의 값에서 +1한 값을 적는다.

3. 위와 마찬가지 방법으로 반복 계산 한다.

4. 최종적으로 APL 값이 같으므로 3이 답이 된다.

 

비슷한 문제로는 https://www.acmicpc.net/problem/9251가 있다.

여기서 크기를 +1 +1 해 준 이유는 첫줄에서 위칸과 왼쪽칸을 계산해야하기 때문이다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] a = br.readLine().toCharArray();
        char[] b = br.readLine().toCharArray();
        int[][] dp = new int[a.length+1][b.length+1];

        for(int i = 1; i <= a.length; i++) {
            for(int j = 1; j <= b.length; j++) {
                if(a[i-1] == b[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        System.out.println(dp[a.length][b.length]);
        br.close();
    }
}

 

참고

사이트 : 위키백과