백준 9251번 - LCS

www.acmicpc.net/problem/9251

9251번: LCS

LCS에 관한 설명은 해당 블로그에 자세히 작성해 놓았습니다.

 

kimtaehyun98.tistory.com/64

Longest Common Subsequence (LCS, 최장 공통 부분 수열)

 

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
 
int LCS[1004][1004];
 
int main(){
    string a, b;
    cin >> a >> b;
    memset(LCS, 0, sizeof(LCS));
    int A = a.size(), B = b.size();
    for (int i = 1; i <= A; i++) {
        for (int j = 1; j <= B; j++) {
            if (a[i-1] == b[j-1]) {
                LCS[i][j] = LCS[i - 1][j - 1] + 1;
            }
            else {
                LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]);
            }
        }
    }
    cout << LCS[A][B] << "\n";
}