DevLog

题目背景与核心痛点

最长公共子串（Longest Common Substring问题要求：求两个字符串的所有子串中能够完全匹配上的最大长度是多少。

例如：s1 = "abcdkkk" 和 s2 = "baabcdadabc"，它们最长的公共子串是 "abcd"，因此最大长度为 4。

如果采用暴力的三层循环枚举，时间复杂度会直接飙升到 $O(N^3)$ 。但如果我们跳出时间维度的纠缠，借用一个二维矩阵表格，利用格子坐标天然隔离两个字符串各自推进的位置，就可以用极其内敛的 $O(N^2)$ 递推轻松破局。

解题思路：二维矩阵的位置隔离与斜向递推

这道题是“利用二维表格天然隔离状态”的教科书级范例：

1. 坐标即位置，格子即状态

我们引入一个二维数组 int a[N][N]。在这个表格里：

横坐标 $i$ 代表第一个字符串 s1 当前推进到了第 $i$ 个字符（对应下标 s1[i-1]）。
纵坐标 $j$ 代表第二个字符串 s2 当前推进到了第 $j$ 个字符（对应下标 s2[j-1]）。
单元格 a[i][j] 的物理含义被严格冻结为：以 s1[i-1] 和 s2[j-1] 这两个字符作为“结尾”的最长公共子串的长度。

2. 斜向连续性的状态转移

公共子串要求字符必须是连续匹配的。这就意味着，当我们在格子 $(i, j)$ 发现当前两个字符相等（s1[i-1] == s2[j-1]）时，能不能让长度加 1，完全取决于它们各自的前一个字符是否也相等。

在二维表格中，s1 的前一个字符和 s2 的前一个字符，其对应的坐标恰好就是当前格子的左上角斜对角格—— a[i-1][j-1]。

如果左上角是 0，说明前面断掉了，当前格子只能自立门户，长度为 0 + 1 = 1。
如果左上角是 3，说明前面已经连续接上了 3 个字符，当前格子顺理成章地续上，长度变为 3 + 1 = 4。

因此，状态转移方程为：

a[i][j] = a[i-1][j-1] + 1;

C 语言代码实现

#include <stdio.h>
#include <string.h>

#define N 256

int f(const char* s1, const char* s2) {
    int a[N][N];
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int i, j;
    
    // 初始化表格，所有格子置 0，天然作为初始边界
    memset(a, 0, sizeof(int) * N * N);
    int max = 0;
    
    // 纵横交错遍历，利用物理位置天然隔离
    for (i = 1; i <= len1; i++) {
        for (j = 1; j <= len2; j++) {
            // 如果当前末尾字符匹配成功
            if (s1[i-1] == s2[j-1]) {
                // 核心状态转移：当前格子的长度由左上角（前一位置的状态）决定
                a[i][j] = a[i-1][j-1] + 1; 
                
                // 动态更新全表最大值
                if (a[i][j] > max) {
                    max = a[i][j];
                }
            }
        }
    }
    
    return max;
}

int main() {
    printf("%d\n", f("abcdkkk", "baabcdadabc"));       // 输出: 4
    printf("%d\n", f("aaakkkabababa", "baabababcdadabc")); // 输出: 5
    printf("%d\n", f("abccbaacbcca", "ccccbbbbbaaaa"));    // 输出: 2
    printf("%d\n", f("abcd", "xyz"));                  // 输出: 0
    printf("%d\n", f("ab", "ab"));                    // 输出: 2
    return 0;
}

💡 蓝桥杯通关·快速复盘

一句话题眼（二维表格的几何美学） 核心本质是 “用斜向物理位置的连续性来映射字符串的连续匹配”。格子的绝对坐标 $(i, j)$ 天然隔离了两个串的字符推进进度。公共子串的“连续性”在二维矩阵里，具象化为了 “一条从左上向右下延伸的对角线连通路径”。只有当路径连续不断时，计数才会累加；一旦字符不匹配，对角线瞬间被截断清零。

防错指南（填表人守则）

下标对齐防呆（Offset 陷阱）：我们在填表格时，为了留出第 0 行和第 0 列作为初始边界，循环是从 1 到 len（表示第 $i$ 个字符）。但在 C 语言中访问字符串数组时，索引是从 0 开始的。因此必须用 s1[i-1] 和 s2[j-1] 进行对齐。切记不要手快写成 s1[i]，否则不仅会漏掉字符串的首字符，还会在访问到最后一个字符时发生数组越界（Out of Bounds）。

地表最强易混点：彻底分清“子串（Substring）”与“子序列（Subsequence）” 这是各大算法比赛中最容易让人翻车的隐形巨坑。两者的物理机制在二维表格的控制下有着本质的不同：

核心概念	连续性要求	不相等时的状态转移方程	二维矩阵中的物理表现
最长公共子串(Substring)	必须严格连续	`a[i][j] = 0;`(也就是保持 `memset` 的初始状态)	孤立的斜对角线。一旦断开就原地清零，无法继承历史遗产，各格子相互独立。
最长公共子序列(Subsequence)	允许非连续	`dp[i][j] = max(dp[i-1][j], dp[i][j-1]);`	全局水流扩散。即使当前字符不匹配，历史的最大匹配长度也会像水流一样，从左边或上边平移继承过来。

💡 深度细节补充：在写子串代码时，由于不相等时格子直接为 0，最大值可能出现在矩阵的任何一个孤立格里，所以我们必须在循环内部用 max 变量去实时捕捉全图的最高点；而写子序列代码时，由于不匹配时会疯狂继承历史遗产，最终的最大值一定会平移汇聚到矩阵的最右下角格子 dp[len1][len2]。

算法美学：从最长公共子串看“二维表格天然隔离位置”的精妙应用