Longest Common Subsequence

Lab C++ Advanced 30 points

Read two strings and print the length of their longest common subsequence.

Input

Two words.

Output

One integer.

Example

Input

ABCBDAB BDCABA

Output

Sample input available Sample output available

Editor

C++

Hints

dp[i][j] = LCS of the first i chars of a and the first j chars of b.

Solution explanation

Comparing two sequences with a 2D table is the idea behind diff.

Show solution

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    string a, b;
    cin >> a >> b;
    vector<vector<int>> dp(a.size() + 1, vector<int>(b.size() + 1, 0));
    for (size_t i = 1; i <= a.size(); i++) {
        for (size_t j = 1; j <= b.size(); j++) {
            dp[i][j] = a[i - 1] == b[j - 1] ? dp[i - 1][j - 1] + 1 : max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    cout << dp[a.size()][b.size()] << "\n";
    return 0;
}

Output

Answer