题解

涉及知识点

1. 动态规划（DP）

   • 定义 $dp[i][j]$ 表示以第一段文本的第 $i$ 个字符和第二段文本的第 $j$ 个字符结尾的最长公共子串长度。
   • 状态转移方程：
     [ dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{如果 } s1[i] = s2[j], \ 0 & \text{否则}. \end{cases} ]

2. 优化空间复杂度

   • 由于 $dp[i][j]$ 只依赖于 $dp[i-1][j-1]$，可以将空间优化为 $O(n)$。

解法代码（C++）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int longestCommonSubstring(const string &s1, const string &s2) {
    int m = s1.length(), n = s2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    int maxLen = 0;
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                maxLen = max(maxLen, dp[i][j]);
            }
        }
    }
    return maxLen;
}

int main() {
    int N;
    cin >> N;
    cin.ignore(); // 忽略第一行的换行符
    while (N--) {
        string s1, s2;
        getline(cin, s1);
        getline(cin, s2);
        int len = longestCommonSubstring(s1, s2);
        cout << "Nejdelsi spolecny retezec ma delku " << len << "." << endl;
    }
    return 0;
}

代码解释

1. 输入处理：
   • 使用 getline 读取每行文本（包含空格）。
2. 动态规划求解：
   • 初始化二维数组 dp，计算以 s1[i] 和 s2[j] 结尾的最长公共子串长度。
   • 维护 maxLen 记录全局最大值。
3. 输出结果：
   • 按照格式输出最长公共子串的长度。

复杂度分析

• 时间复杂度：$O(m \times n)$，其中 $m$ 和 $n$ 是两段文本的长度。
• 空间复杂度：$O(m \times n)$（可优化为 $O(n)$）。

总结

本题通过动态规划高效求解最长公共子串问题，适用于文本相似性检测等场景。