#include<bits/stdc++.h>
using namespace std;
const int z = 1024;
int LIS(int *data) {
    int len = 0, linedp[z];
    for(int i = 2;i <= data[0];++i) {
        linedp[i] = 1;
        for(int j = 1;j < i;++j)
            if(data[i] > data[j]&&linedp[i] < linedp[j]+1)
                linedp[i] = linedp[j]+1;
        len = max(linedp[i],len);
    }
    return len;
    //最少链划分 = 最长反链长度；
}//最长上升子序列 
int LCST(char *data,char *datb) {
    int k = 0, linedp[2][z];
    memset(linedp,0,sizeof(linedp));
    for(int i = 0;i < strlen(data);++i) {
        k = !k;
        for(int j = 0;j < strlen(datb);++j)
            if(data[i] == datb[j])
                linedp[k][j] = linedp[!k][j-1]+1;
            else
                linedp[k][j] = max(linedp[k][j-1],linedp[!k][j]);
    }
    return linedp[k][strlen(datb)-1];
}//最长公共字串； 
int LCSQ(char *data,char *datb) {
    int k = 0, linedp[2][z], len = 0;
    memset(linedp,0,sizeof(linedp));
    for(int i = 0;i < strlen(data);++i) {
        memset(linedp[!k],0,sizeof(linedp[!k]));
        k = !k;
        for(int j = 0;j < strlen(datb);++j)
            if(data[i] == datb[j]) {
                linedp[k][j] = linedp[!k][j-1]+1;
                len = max(len,linedp[k][j]);
            }
    }
    return len;
}//最长公共子序列； 
int LCIS(char *data,char *datb) {
    int linedp[z], k = 0;
    memset(linedp,0,sizeof(linedp));
    for(int i = 0;i < strlen(data);++i) {
        int ans = 0;
        for(int j = 0;j < strlen(datb);++j) {
            if(data[i] > datb[j])
                ans = max(ans,linedp[j]);
            if(data[i] == datb[j])
                linedp[j] = ans+1;
        }
    }
    return linedp[strlen(datb)-1];
}//最长严格上升公共子序列； 
signed main() {
    char a[z], b[z];
    scanf("%s %s",a,b);
    printf("%d",LCIS(a,b));
    //to do;
}//駄作;