#!/bin/python3

def commonChild(s1, s2):
    # tests timeout due to local variable access: https://stackoverflow.com/questions/11241523/why-does-python-code-run-faster-in-a-function
    m = len(s1)
    n = len(s2)    
    dp = [[0] * 5001 for i in range(5001)] 
    for i in range(m):
        for j in range(n):
            if s1[i] == s2[j]:
                dp[i+1][j+1] = dp[i][j] + 1     
            else:       
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
    return dp[m][n]

# C++
#include <bits/stdc++.h>

using namespace std;

int commonChild(string s1, string s2) {
    int m = s1.length();
    int n = s2.length();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (s1[i] == s2[j]) 
                dp[i+1][j+1] = dp[i][j] + 1;
            else
                dp[i+1][j+1] = max(dp[i][j+1], d[i+1][j]);
        }
    }
    return dp[m][n];
}
