Challenge: Longest Common Subsequence

Lab C++ Intermediate 20 points

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

Input

Two words (at most 1000 letters each).

Output

One number.

Example

Input

abcde
ace

Output

Sample input available Sample output available

Editor

C++

Hints

Match: dp[i-1][j-1] + 1.

No match: max(dp[i-1][j], dp[i][j-1]).

Solution explanation

O(n × m) time and memory.

Show solution

#include <algorithm>
#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()] << endl;
    return 0;
}

Output

Answer