#include <cstdio>
#include <iostream>
#include <algorithm>
#include "cstdio"
using namespace std;
                  /// 集合 : a的前i 个字母,b的前j个字母 中所有公共子序列
                  /// 属性: 长度最大值 max
                  /// 状态 转移:  00 01 10 11 , 代表 a的第i 个字母,b的第j个字母包含不包含在公共子序列中
                  /// 00: f[i-1][j-1]   01 10 不好表示 ,可以用 包含这两个的集合来算 ,因为 f[i][j] 包含 f[i-1][j] 包含 01 , 以此类推10 , 求 max 可以有重复 ,只要不漏掉状态就可以,因为多个重复取最大值 仍然不变
                  /// 且 00 的f[i-1][j-1] 也可以省略 ,因为 f[i-1][j-1] 包含在 f[i][j-1] 和 f[i-1][j] 当中
const int N=1010;
int n,m;
int f[N][N];
char s1[N],s2[N];

int main() {
    cin >> n >> m;
    scanf("%s%s",s1+1,s2+1);

    for(int i=1; i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j] = max(f[i-1][j],f[i][j-1]);
            if(s1[i] == s2[j])
            f[i][j] = max (f[i][j] , f[i-1][j-1]+1);

        }

    }


    cout <<f[n][m]<< endl;


    return 0;


   






}
// 64 位输出请用 printf("%lld")

两个子串

一般就是  在第一个序列的 前i 个字母中出现 ,且在第二个序列的前j 个字母中出现的子序列

 

状态转移:

a[i] 和 b[j]是否 包含在子序列当中?

 00 01 11 11

其中: 00,代表a[i] b[j]都不包含在子序列当中 ,那么

这片划分的 状态就是 f[i-1][j-1]

01,代表 a[i]不包含在子序列当中 ,但 b[j] 一定包含在子序列中 ,但是 f[i-1][j]的意思是 在第一个序列的前i-1个字母中出现,且在第二个序列的前j个字母中出现的子序列的全集 中的最长子序列 , 也就是 f[i-1][j] 是包含 01这种情况的, 因为  f[i-1][j] ,b[j]不一定就包含在公共子序列中.

10情况与01类似:

图解表示:

 

 

11 ,只有当 a[i] == b[j] 时, 这种情况才参与到max比较

这种状态为 f[i-1][j-1] + 1;

 

00: 可以不用写 ,因为 f[i-1][j-1]包含在 f[i-1][j] 和 f[i][j-1] 当中,