#include <iostream>
#include <fstream>
#include <vector>
#include <random>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;

typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<pair<int,int>> VII;

template<typename T>
void print(vector<T> sez) {
    for (T x : sez) cout << x << " ";
    cout << endl;
}

int fib(int n) {
    if (n<=1) return n;
    return fib(n-1)+fib(n-2);
}

int memo[1001];

int fib2(int n) {
    if (n<=1) return n;
    if (memo[n]>0) return memo[n];
    memo[n] = fib2(n-1)+fib2(n-2);
    return memo[n];
}

int inf=1e9;
int a=3,b=4;
int mem_jump[100];

int jump(int i, vector<int> &x) {
    int n=x.size();
    if (i==n-1) return 0;
    if (mem_jump[i]) return mem_jump[i];
    int best=inf;
    for (int j=i+1;j<n;j++) {
        int d=x[j]-x[i];
        if (a<=d && d<=b) {
            best=min(best,1+jump(j,x));
        }
    }
    mem_jump[i]=best;
    return best;
}


int main() {
    /*
    for (int n=0;n<=10;n++) {
        cout << n << ": " << fib(n) << endl; 
    }
    //cout << fib(100) << endl;
    cout << fib2(10) << endl;
    cout << fib2(100) << endl;

    int fib3[1000];
    fib3[0]=0;
    fib3[1]=1;
    for (int n=2;n<=100;n++) {
        fib3[n]=fib3[n-1]+fib3[n-2];
    }
    cout << fib3[100] << endl;

    int f2=0, f1=1;
    for (int n=2;n<=100;n++) {
        int fn=f1+f2;
        f2=f1;
        f1=fn;
    }
    cout << f1 << endl;
    */
    /*
    vector<int> x={0,3,4,6,10};
    cout << jump(0,x) << endl;
    */
    /*
    vector<int> c = {0,2,5,6,9,15,16,17,20};
    int N=8;
    int f[100];
    f[0]=0;
    for (int n=1;n<=N;n++) {
        f[n]=0;
        for (int x=1;x<=n;x++) {
            f[n]=max(f[n], f[n-x]+c[x]);
        }
    }
    cout << f[N] << endl;
    int n=N;
    while (n>0) {
        for (int x=1;x<=n;x++) {
            if (f[n]==f[n-x]+c[x]) {
                cout << x << endl;
                n-=x;
                break;
            }
        }
    }
    */
    /*
    vector<string> t={".#....",
                      "....#.",
                      ".#..#.",
                      "......"};
    int h=t.size(), w=t[0].size();
    int f[10][10];
    memset(f,0,sizeof(f));
    for (int i=h-1;i>=0;i--) {
        for (int j=w-1;j>=0;j--) {
            if (i==h-1 && j==w-1) f[i][j]=1;
            else if (t[i][j]=='#') f[i][j]=0;
            else f[i][j] = f[i+1][j] + f[i][j+1];
        }
    }
    cout << f[0][0] << endl;
    */
    string s="ABCBDAB";
    string t="BDCBBA";
    int n=s.size(), m=t.size();
    int lcs[20][20];
    memset(lcs,0,sizeof(lcs));
    for (int i=n-1;i>=0;i--) {
        for (int j=m-1;j>=0;j--) {
            lcs[i][j]=max(lcs[i+1][j], lcs[i][j+1]);
            if (s[i]==t[j]) {
                lcs[i][j]=max(lcs[i][j], 1+lcs[i+1][j+1]);
            }
        }
    }
    for (int i=0;i<=n;i++) {
        for (int j=0;j<=m;j++) {
            cout << lcs[i][j] << " ";
        }
        cout << endl;
    }
    cout << lcs[0][0] << endl;
    string l="";
    int i=0,j=0;
    while (i<n && j<m) {
        if (lcs[i][j]==lcs[i+1][j]) i++;
        else if (lcs[i][j]==lcs[i][j+1]) j++;
        else {
            l+=s[i];
            i++; j++;
        }
    }
    cout << l << endl;
    return 0;
}