最长公共子串

📘 题目描述

给定两个字符串 $s,t$，求出它们的最长公共 子串 长度。字符串长度 $1\leq |s|,|t|\leq 2000$。

💡 解题思路

🔢 状态定义

• $f_{i,j}$ 表示字符串 $s$ 以 $i$ 结尾和字符串 $t$ 以 $j$ 结尾的最长公共子串长度。

🔁 状态转移

• 如果 $s[i] = t[j]$，则 $f_{i,j} = f_{i-1,j-1} + 1$。
• 否则，$f_{i,j} = 0$。这意味着同时结尾无法形成公共子串，因为此时 $s[i]\not= t[j]$。

综上：

\[ f_{i,j} = \begin{cases} f_{i-1,j-1} + 1, & \text{if } s[i] = t[j] \\ 0, & \text{otherwise} \end{cases} \]

🟡 初始化：

初始化时，$f_{i,0} = 0$，$f_{0,j} = 0$。

• 含义：当字符串 $s$ 为空时，最长公共子串长度为 $0$。同理当 $t$ 为空时，最长公共子串长度为 $0$。

✅ 统计答案

• $ans=\max(f_{1,1},f_{1,2},\ldots,f_{1,m},\ldots,f_{n,m})$。

⏱️复杂度分析

• 时间复杂度：$O(n\cdot m)$。
• 空间复杂度：$O(n\cdot m)$。

✅ 代码实现

int n = s.size(), m = t.size();
s = " " + s, t = " " + t;
for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= m; j++)
    {
        if (s[i] == t[j])
        {
            f[i][j] = f[i - 1][j - 1] + 1;
        }
        ans = max(ans, f[i][j]);
    }
}