백준, BOJ, 5582번, 공통 부분 문자열 C++ [CPP] ★★★

이 문제는 알고리즘을 알 경우 쉽게 풀 수 있다.

쉽게 생각하기는 어려운데

알고 있다면 바로 풀 수 있다.

 

 

 

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

5582번: 공통 부분 문자열

 

 

---

 

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;


//LCS[i][j] => s1의 i번째 문자열과 s2의 j번째 문자열까지의 최장 공통 문자열수
int LCS[4001][4001];

int main(){
    string s1,s2;
    cin >> s1 >> s2;
    int sz1,sz2;
    sz1 = s1.size();
    sz2 = s2.size();
    
    int maxans = 0;
    for(int i = 1; i<=sz1; i++){
        for(int j = 1; j<=sz2; j++){
            //문자열이 없으면 0
            
            if(s1[i-1] == s2[j-1]){
                LCS[i][j] = LCS[i-1][j-1] + 1;
                //i,j가 같다면 이전까지의 최장 공통 문자열에 1개 더 연속한 것임
                //처음으로 같더라도 0으로초기화되었기 때문에 1로됨
            }else{
                LCS[i][j] = 0;
                //문자열이 다르다면 연속하지 않으므로 이제 다시 0번째부터 다시 시작해야함.
            }
            maxans = max(maxans, LCS[i][j]);
        }
    }
    
    cout << maxans << '\n';
    

    return 0;
}

 

여기서 주의할 점은.

LCS의 배열은 0부터 쓰되

사용은 1부터 한다는 것

i와 j의 범위를 조심해야하고 최장 공통 문자열이란 것에 대해서 쉽게 말하자면

 

1. 맨 앞에서부터 일치하는지 본다.

2. 일치하지 않으면 연속하지 않으므로 그 떄까지 최장 문자열은 0이다. 다만 다른 문자열과는 연속할 수 있으므로 다른 문자열의 index를 +1만큼 늘리고 다시 비교한다.

3. 일치하면 이전의 최장문자열 길이 +1을 한다. 일치해도 다른 문자열과도 연속하는지 알아보기 위해 문자열의 index를 +1만큼 늘린다.

쉽게 말하면 저것이다.

이 방식은 Bottom-Up 방식이라고 보면된다.

즉 마지막 LCS[i][j] 는 첫번째 문자열 i번째까지, 두번째 문자열 j번째까지의 최장 공통 문자열이다.

LCS[i][j]는 다시 말해서 끝이 [i]이고 [j]인 최장 공통 문자열이다.

 

즉, 위 문제의 답은 LCS[i][j]를 구하는 것이 아니라. LCS[i][j]까지 구하되 그 중 가장 최댓값을 구하는 것이다.