//
//  main.cpp
//  Longest Common Subsequence
//
//  Created by Himanshu on 17/09/21.
//

#include <iostream>

#include <iostream>
using namespace std;

void LCS (string s1, string s2) {
    int N = (int)s1.size(), M = (int)s2.size();
    int L[N+1][M+1];

    for (int i=0; i<=N; i++) {
        for (int j=0; j<=M; j++) {
            L[i][j] = 0;
        }
    }

    for (int i=0; i<=N; i++) {
        for (int j=0; j<=M; j++) {
            if (i == 0 || j == 0) {
                L[i][j] = 0;
            } else if (s1[i-1] == s2[j-1]) {
                L[i][j] = L[i-1][j-1] + 1;
            } else {
                L[i][j] = max(L[i][j-1], L[i-1][j]);
            }
        }
    }
    
    cout<<"Length of Longest Common Subsequence (LCS) is: "<<L[N][M]<<endl;
    
}
 
int main() {
    string s1 = "abcde", s2 = "ace";
    LCS(s1, s2);
}