import java.util.*;

/**
在最长公共子序列（LCS）问题中，设计出 `dp[i][j]` 这样的二维动态规划数组，是基于对问题本质的分析和动态规划思想的自然推导。具体思路可以拆解为以下几步：


### 1. 首先理解问题的核心矛盾
LCS 问题要解决的是：**两个字符串中，找出长度最长的、顺序一致但不要求连续的公共子序列**。  
例如 `str1="abcbdab"` 和 `str2="bdcaba"`，LCS 是 `"bcab"` 或 `"bdab"`，长度为 4。  

关键矛盾在于：**子序列的“不连续性”和“顺序一致性”** 导致无法用简单的遍历解决，必须记录中间状态才能逐步推导。


### 2. 从“子问题”入手（动态规划的核心思想）
动态规划的本质是**将复杂问题拆解为可重复解决的子问题**，并通过记录子问题的解来避免重复计算。  

对于 LCS 问题，最自然的子问题拆分方式是：  
- 考虑 `str1` 的前 `i` 个字符（`str1[0..i-1]`）和 `str2` 的前 `j` 个字符（`str2[0..j-1]`）  
- 计算这两个“前缀子串”的 LCS 长度  

为什么这样拆分？因为：  
- 整个问题的解（完整字符串的 LCS）可以由这些子问题的解组合而来  
- 子问题之间存在重叠（例如计算 `i=3,j=4` 时可能用到 `i=2,j=3` 的结果）  


### 3. 定义状态：用 `dp[i][j]` 表示子问题的解
基于上述子问题，直接定义状态：  
`dp[i][j]` = 字符串 `str1` 的前 `i` 个字符与 `str2` 的前 `j` 个字符的 LCS 长度。  

为什么需要二维？因为子问题的边界由**两个独立变量**确定：`i`（`str1` 的前缀长度）和 `j`（`str2` 的前缀长度）。少了任何一个维度，都无法唯一确定子问题的范围。  


### 4. 推导状态转移方程（如何用子问题解求当前问题解）
确定状态后，需要找到 `dp[i][j]` 与更小的子问题（如 `dp[i-1][j]`、`dp[i][j-1]`、`dp[i-1][j-1]`）之间的关系。  

分两种情况分析：  
- **情况1：`str1[i-1] == str2[j-1]`（当前字符相同）**  
  这两个字符可以直接加入 LCS 中，因此当前 LCS 长度 = 两个字符串各去掉最后一个字符后的 LCS 长度 + 1，即：  
  `dp[i][j] = dp[i-1][j-1] + 1`  

- **情况2：`str1[i-1] != str2[j-1]`（当前字符不同）**  
  两个字符无法同时加入 LCS，因此当前 LCS 长度取决于“去掉 `str1` 最后一个字符”或“去掉 `str2` 最后一个字符”两种情况的最大值，即：  
  `dp[i][j] = max(dp[i-1][j], dp[i][j-1])`  


### 5. 确定初始状态（最小子问题的解）
当 `i=0` 或 `j=0` 时（即其中一个字符串为空），LCS 长度必然为 0。因此：  
`dp[0][j] = 0`（对任意 `j`）  
`dp[i][0] = 0`（对任意 `i`）  


### 6. 最终解的位置
整个问题的解是两个完整字符串的 LCS 长度，即 `dp[str1.length][str2.length]`。  


### 总结：为什么这样设计 `dp` 数组？
1. **问题特性决定维度**：LCS 涉及两个独立字符串的匹配，必须用两个维度（`i` 和 `j`）分别表示它们的前缀范围。  
2. **子问题自然拆分**：拆分前缀子串的 LCS 是最直观的子问题划分方式，能覆盖所有可能的匹配情况。  
3. **状态转移逻辑自洽**：通过当前字符是否相同的两种情况，能清晰地用更小的子问题解推导出当前解。  

这种设计是动态规划“拆分问题→定义状态→寻找转移关系”思想的典型应用，也是解决“两个序列匹配”类问题的通用思路（如编辑距离、最长重复子数组等均采用类似的二维 DP 设计）。
**/
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int len1 = in.nextInt();
        int len2 = in.nextInt();
        // 注意 hasNext 和 hasNextLine 的区别
        String str1 = in.next();
        String str2 = in.next();
        char[] cs1 = str1.toCharArray();
        char[] cs2 = str2.toCharArray();
        // 字符串str1的前i个字符与字符串str2的前j个字符的最长公共子序列长度
        int[][] dp = new int[cs1.length + 1][cs2.length + 1];
        for(int i = 1; i <= cs1.length; i++){
            for(int j = 1; j <= cs2.length; j++){
                // 若当前字符相同
                if(cs1[i - 1] == cs2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                // 若当前字符不同，最长公共子序列长度取决于 “去掉 str1 最后一个字符” 或 “去掉 str2 最后一个字符” 两种情况的最大值，
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        System.out.println(dp[cs1.length][cs2.length]);
    }
}