백준 5582: 공통부분 문자열 [Java] -포포

문제

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.

어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.

두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공통 부분 문자열은 빈 문자열이다.

입력

첫째 줄과 둘째 줄에 문자열이 주어진다. 문자열은 대문자로 구성되어 있으며, 길이는 1 이상 4000 이하이다.

출력

첫째 줄에 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 출력한다.

예제 입력 1 

ABRACADABRA
ECADADABRBCRDARA

예제 출력 1 

5

예제 입력 2 

UPWJCIRUCAXIIRGL
SBQNYBSBZDFNEV

예제 출력 2 

0

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

5582번: 공통 부분 문자열

---

오늘은 문자열 한 문제를 풀겠다고 다짐하고 고른 문제다.
근데 문제 이름부터 '공통 부분 문자열'을 보니 DP에 최장 증가 수열(LIS)가 떠올랐다.

먼저 문자열로 풀어보려고 코드를 작성해봤다.
참고로 시간초과 뜬 오답코드다.

package com.company.string;

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

public class Main {
    static int max = 0;
    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 n = s1.length();
        int m = s2.length();
        for (int i = 0; i < n; i++) {
            char c = s1.charAt(i);

            for (int j = 0; j < m; j++) {
                if (s2.charAt(j) == c) {
                    int count = 1;
                    int nextN = i+1;
                    int nextM = j+1;

                    while (true) {
                        if(nextN == n || nextM == m){
                            max = Math.max(count, max);
                            break;
                        }
                        if (s1.charAt(nextN) == s2.charAt(nextM)) {
                            count ++;

                            nextN ++;
                            nextM ++;
                        } else{
                            max = Math.max(count, max);
                            break;
                        }
                    }
                }
            }
        }
        System.out.println(max);
    }
}

문자열 길이가 최대 4000으로 주어진다. 
위의 로직은 s1의 길이만큼 반복하면서 s1.charAt(i)번째 알파벳과 동일한 알파벳이 s2에 있다면 각각 다음 알파벳이 동일한지 검사하게된다.
제출하면 20%까지 서서히 오르더니
'설마 이게 되나?' 하는 순간 퍼센티지가 멈추고 시간초과가 발생하게 된다.

n이 4000인데 완전 탐색을 실행하니 어쩔 수 없다.  

---

DP로 접근

최장 증가 수열(LIS)와 비슷하게 접근했다.
LIS 알고리즘을 잘 모른다면 아래 두 문제를 풀어보면서 익히는 것을 추천한다!
https://www.acmicpc.net/problem/11055

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

만약 s1.charAt(i) == s2.charAt(j) 라면,
dp[ i ][ j ] = dp[i-1][j-1] + 1;
처리를 해주는 방식이다. 

 

String s1 = "ABDEGF"
String s2 = "DBADEGA"

위의 그림과 같이 표현할 수 있다.
만약 s1.charAt(i) == s2.charAt(j) 라면
dp[ i ][ j ] = dp[i-1][j-1] + 1 이 된다.
dp[i-1][j-1]은 두 문자열에서 각각 i, j번째 문자열의 직전 알파벳까지 몇 개의 문자열이 동일했는지의 정보를 담고 있기 때문이다.

package com.company.string;

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

public class Main {
    static int map[][];
    static int max = 0;
    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 n = s1.length();
        int m = s2.length();
        map = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    map[i][j] = map[i-1][j-1] + 1;
                    max = Math.max(map[i][j], max);
                }
            }
        }

        System.out.println(max);
    }
}

 

혹시 문자열로 해결한 풀이가 있나 하고 검색해봤는데 전부 다 DP로 해결했더라..