[Algorithm] 9252: LCS 2

📦9252: LCS 2

---

[알고리즘 풀이] 강동규
Reviewed by Kade Kang (devkade12@gmail.com)
Reviewed:: 2024-02-19
문제 확인하기

풀이

• LCS(최장 공통 부분 수열)은 알고리즘이 정해져 있다.
• 관련된 알고리즘에 대한 내용은 LCS 위키백과 다음을 참고하자.
• LCS는 이전값의 내용을 참고하기 때문에 인덱스 0의 부분이 비어 있어야 한다. 때문에 s1, s2에 ’ ‘를 붙여준다.
• 백트레킹을 하면서 넘어가기 전 문자를 저장한다.

#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
#define endl '\n'
using namespace std;
 
int LCS[1002][1002];
string s1, s2;
stack<char> st;
 
void Input(){
    cin >> s1 >> s2;
}
 
void Solution(){
    s1 = ' ' + s1;
    s2 = ' ' + s2;
    for(int i=1; i<s1.length(); i++){
        for(int j=1; j<s2.length(); j++){
            if(s1[i] == s2[j])
                LCS[i][j] = LCS[i-1][j-1]+1;
            else{
                LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]);
            }
        }
    }
    int i = s1.length()-1;
    int j = s2.length()-1;
    while(LCS[i][j]){
        if(LCS[i][j] == LCS[i-1][j]){
            i--;
        }
        else if(LCS[i][j] == LCS[i][j-1]){
            j--;
        }
        else{
            st.push(s1[i]);
            i--;j--;
        }
    }
 
    cout << LCS[s1.length()-1][s2.length()-1] << endl;
    while(!st.empty()){
        cout << st.top();
        st.pop();
    }
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    Input();
    Solution();
 
    return 0;
}