[Beakjoon] 5582 공통 부분 문자열 (Java)

문제 링크

BOJ 5582 : 공통 부분 문자열

문제

두 문자열이 주어졌을 때,
두 문자열의 부분 문자열 중, 공통되는 가장 긴 문자열의 길이를 출력한다.

풀이

LCS알고리즘을 이용한다.
[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

LCS는 dp 알고리즘의 한 종류로, 공통 부분 문자열을 찾는데 사용된다.

문자열 s1,s2가 존재하고 각각 i번째 j번째 문자열을 비교하는 상황이라면, 두가지 경우가 존재한다.

1. i번째 문자와 j번째 문자가 일치하는 경우

2. i번째 문자와 j번째 문자가 일치하지 않는 경우

dp배열에는 i번째 문자와 j번째 문자를 끝으로 할 때 가장 긴 공통 부분 문자열의 길이를 저장한다.
그러므로 2번의 경우는 0이 저장된다. 비교하는 문자가 다를 경우 공통 부분 문자열이 될 수 없기 때문이다.

이제 1번의 경우를 생각해보면, 공통 부분 문자열은 모두 연속된 경우이므로 i번째와 j번째를 끝으로 하는 문자열의 최대 길이는 i-1번째와 j-1번째 문자열을 끝으로 하는 공통 문자열의 최대 길이 +1이 된다.

점화식

	if(s1.charAt(i) == s2.charAt(j)) {
    	dp[i][j] = dp[i-1][j-1] + 1;
    }
    else {
    	dp[i][j] = 0;
    }

코드

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));
        String s1 = br.readLine();
        String s2 = br.readLine();

        int answer = 0;
        int[][] dp = new int[s1.length()+1][s2.length()+1];
        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < s2.length(); j++) {
                if(i==0||j==0) {
                    if(s1.charAt(i) == s2.charAt(j)) {
                        dp[i][j] = 1;
                    }
                    else {
                        dp[i][j] = 0;
                    }
                }
                else {
                    if(s1.charAt(i) == s2.charAt(j)) {
                        dp[i][j] = dp[i-1][j-1] + 1;
                    }
                    else {
                        dp[i][j] = 0;
                    }
                }
                answer = Math.max(answer, dp[i][j]);
            }
        }

        System.out.println(answer);
    }
}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));
        String s1 = br.readLine();
        String s2 = br.readLine();

        int answer = 0;
        int[][] dp = new int[s1.length()+1][s2.length()+1];
        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < s2.length(); j++) {
                if(i==0||j==0) {
                    if(s1.charAt(i) == s2.charAt(j)) {
                        dp[i][j] = 1;
                    }
                    else {
                        dp[i][j] = 0;
                    }
                }
                else {
                    if(s1.charAt(i) == s2.charAt(j)) {
                        dp[i][j] = dp[i-1][j-1] + 1;
                    }
                    else {
                        dp[i][j] = 0;
                    }
                }
                answer = Math.max(answer, dp[i][j]);
            }
        }

        System.out.println(answer);
    }
}