백준 09252 - LCS 2

출처 : https://www.acmicpc.net/problem/9252 

9252번: LCS 2

 

고려사항

• 동적 프로그래밍 LCS 알고리즘을 응용하여 제일 긴 부분 문자열의 요소들을 뽑아내는 문제.
• lcs 를 재귀로 풀 수도 있고( 09251 - LCS ), 이 문제처럼 bottom -> top 으로 반복문으로도 풀 수 있다.
  재귀는 top -> down 이다!
• 현재 조사중인 str1 의 인덱스 y 와 str2의 인덱스 x 들의 문자가 같으면 lcs[y-1][x-1] + 1,
  다르면 lcs[y-1][x], lcs[y][x-1] 중 큰 값으로 기입을 해가며 lcs 를 채워나가면,
  lcs[str1Len][str2Len] 의 값이 가장 긴 부분 문자열의 길이 이다.
  (str의 인덱스는 0부터 시작하지만, lcs를 편하게 채우기 위해서 보통 첫 행과 첫 열은 0으로 패딩해주기 때문에
  인덱스 계산에 주의하자!!!!!!)
  
  
• 문자열 길이를 구하고 나서는, 각각의 요소들을 뽑기 위해선, lcs[str1Len][str2Len] 부터,
  str1[y] == str2[x] 라면 정답 문자열에 원소를 추가하고 두 인덱스 모두 -1 해주고,
  서로 다르다면 lcs[y-1][x], lcs[y][x-1] 중 lcs[y][x] 와 같은 값을 지닌 방향으로 인덱스를 수정해주며
  lcs값이 0이 될 때까지 진행해 주면 된다.
  ( 앞에서 가장 긴 부분 문자열 길이리를 구했던 방식을 되돌아가는 방식이다! )
• 정답 문자열을 뒤집어서 출력해주면 끝!

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int lcs[1001][1001];
 
int main() {
    string str1, str2, ans;
    int maxLen, str1Len, str2Len, y, x;
    cin>>str1>>str2;
 
    str1Len = str1.length();
    str2Len = str2.length();
    y = str1Len;
    x = str2Len;
    for(int i=0;i<str1Len;++i){
        for(int j=0;j<str2Len;++j){
            if(str1[i] == str2[j]){
                lcs[i+1][j+1] = lcs[i][j] + 1;
            }else{
                lcs[i+1][j+1] = max(lcs[i][j+1], lcs[i+1][j]);
            }
        }
    }
 
    maxLen = lcs[str1Len][str2Len];
    cout<<maxLen<<"\n";
 
    if(maxLen){
        while(lcs[y][x] != 0){
            if(str1[y-1] == str2[x-1]){
                ans.push_back(str1[y-1]);
                --y, --x;
            }else{
                if(lcs[y-1][x] == lcs[y][x]){
                    --y;
                }else{
                    --x;
                }
            }
        }
 
        reverse(ans.begin(), ans.end());
        cout<<ans;
    }
 
    return 0;
}