你好，我是阿西莫夫。

在生物进化论中，判断两个物种亲缘关系远近的金标准是DNA 序列的相似度。

如果两个物种的 DNA 序列中，有很长一段是相同的（即使中间插入了其他突变碱基），我们就认为它们拥有共同的祖先，这就是 “同源性（Homology）”。

在计算机科学中，这个问题被抽象为 “最长公共子序列（Longest Common Subsequence, LCS）”。它是二维动态规划最经典的入门题，完美诠释了如何通过构建二维矩阵来解决两个字符串之间的决策问题。

[OI 题库] 寻找同源基因 (The Homologous Gene Search)

题目背景

“生命是一本用 A、T、C、G 四个字母写成的史书，每一次进化都在上面留下了修改的痕迹。”

生物学家在亚马逊发现了一种古老的两栖动物，怀疑它是现代某种青蛙的祖先。为了验证这一假说，科学家提取了古生物的 DNA 片段（序列 X）和现代青蛙的 DNA 片段（序列 Y）。

由于进化的过程中会发生碱基的插入、删除或替换，两条序列长度可能不同，且相同的片段可能不再连续。 例如：

• 祖先：A T C G
• 后代：A T (插入 A) C (替换 T) G $\to$ A T A C G

我们需要找到这两条序列中顺序一致且长度最长的公共碱基序列（即“最长公共子序列”），该序列的长度越长，说明亲缘关系越近。

题目描述

给定两个由字符 A, T, C, G 组成的字符串 $S_1$和 $S_2$。 请计算它们的最长公共子序列（LCS）的长度。

定义：

• 子序列：从原字符串中删除若干个（也可以不删）字符，但不改变剩余字符相对顺序形成的新字符串。
  • 例如：ACGT 的子序列包括 AG、AT、ACGT 等，但不包括 CA（顺序反了）。
• 公共子序列：既是 $S_1$ 的子序列，又是 $S_2$ 的子序列。

输入格式

第一行一个字符串 $S_1$。 第二行一个字符串 $S_2$。

输出格式

一个整数，表示最长公共子序列的长度。

样例数据

样例 1

ATCGA
ATACA

4

解析：

最长公共子序列是 ATCA。 匹配路径： A (位置1) - A (位置1) T (位置2) - T (位置2) C (位置3) - C (位置4) A (位置5) - A (位置5) 长度为 4。

样例 2 (完全不匹配)

AAAA
TTTT

0

样例 3 (包含插入)

GCTAGT
GCT

3

数据范围

• 字符串长度 $|S_1|, |S_2| \le 1000$。
• 考察点：典型的二维 DP，$O(N^2)$ 复杂度。