[백준] 5582번 - 공통 부분 문자열

1. 문제 이해

입력으로 두 문자열의 주어지면, 해당 문자열의 공통된 부분 문자열의 길이를 구하는 문제이다.

 

 

---

2. 문제 풀이

하나의 문자열을 기준으로, 나머지 문자열을 짧게 보면서 문자열의길이를 구한다.

DP로 풀기위해 문자열의 길이를 쪼개가며 계산한다. 연속된 문자열 이므로, 경우의 수는 각 문자열 길이의 곱이다.

최대 길이만 구하면 되지만, 길이가 달라지면서, 길이가 같은 일치하는 부분문자열이 여러개 생길 수 있으므로 길이를 계속 저장한다.

 

예제 입력 1 

ABRACADABRA
ECADADABRBCRDARA

 

ABRACADABRA
E

길이0 =  E까지 봤을 때, 가장 긴 부분 문자열 길이

 

ABRACADABRA
EC

길이 1 = C까지 봤을 때, 가장 긴 부분 문자열 길이

 

ABRACADABRA
ECA

길이 1

 

ABRACADABRA
ECAD

길이2 = ABRACA와 ECA일때 의 길이 1에 1을 더해준다.

 

ABRACADABRA
ECADA

길이3 =  ABRACAD와 ECAD 일때의 길이 2에 1을 더해준다.

 

ABRACADABRA
ECADAD

길이2 

D가 새롭게 들어오면서 ABRACAD  와 ECADAD 인 경우도 경우도 생겼다. 이 경우 길이가 2가 되는데

ABRACA 와 ECADA 일때의 길이 1에 1을 더해준다.

 

편의성을 위해 기준 문자열의 길이를 항상 똑같이 했지만, 모든 길이에 대응되는 공통 부분문자열의 길이를 저장해둬야 한다. 즉, 문자열의길이가 최대 4000이므로, 계산해야되는 경우는 4000*4000 번이다.

 

 

ABRACADABRA
ECADADA

길이3

 

ABRACADABRA
ECADADAB

길이4 = ABRACADA 와 ECADADA 일때의 길이 3에 1을 더해준다.

 

ABRACADABRA
ECADADABR

길이5 = ABRACADAB 와 ECADADAR 일때의 길이 4에 1을 더해준다.

 

ABRACADABRA
ECADADABRB

길이1

 

ABRACADABRA
ECADADABRBC

길이1

 

이 과정을 모두 반복하면, 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 구할 수 있다.

 

---

3. 제출 결과

 

---

4. 문제 코드

 

#include <bits/stdc++.h>
using namespace std;
int dp[4001][4001];
int main(){
    string st1, st2;
    cin >> st1 >> st2;

    int st1Len = st1.length();
    int st2Len = st2.length();

    int maxLen = 0;

    for(int i=0;i<st1Len; i++) {
        for(int j=0; j<st2Len; j++) {
            if(st1[i] == st2[j]) {
                if(i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                maxLen = max(maxLen, dp[i][j]);
            }
        }
    }

    cout << maxLen;

}