机试题——D路通信

题目描述

现在老师给了他们一个D路通信。他们面对的通信链路有如下几个性质：

• 高斯噪声性：如果发出一段字符串作为消息，消息的开始前和结束后可能会出现随机高斯噪声。
• 内容完整性：该过程不会丢失任何字符，字符顺序也不会发生变化。
• 字符统一性：所有的消息内容和噪声都是小写字符。

依据链路的特点，想到了一种消除高斯噪声的算法：

• 同时采用两条含有随机噪声的链路发出一段消息。
• 在接收侧，在接收到的两条消息当中寻找最长的那段连续公共子串，就是有效信息。

现在想求有效消息的长度，注意有效消息不一定是唯一的，也有可能为空，只需要返回消息的长度。

输入描述

两行分别代表两个字符串，分别为两条链路收到的信息，仅包含小写字母。

• 输入的字符串长度范围为 (0 < len \leq 1000)。

输出描述

一行，一个数字，以回车结束，表示有效信息的长度。

用例输入

vsavvzxaaxvzvz
zzczcaaa

2

解题思路

问题分析

我们需要找到两个字符串的最长公共子串。动态规划是解决这类问题的经典方法。具体思路如下：

1. 定义状态：

   • 使用一个二维数组 dp[i][j] 表示字符串 s1 的前 i 个字符和字符串 s2 的前 j 个字符的最长公共子串长度。

2. 状态转移：

   • 如果 s1[i-1] == s2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。
   • 否则，dp[i][j] = 0，因为公共子串必须是连续的。

3. 初始化：

   • dp[0][j] = 0 和 dp[i][0] = 0，因为任何字符串与空字符串的最长公共子串长度为 0。

4. 结果：

   • 遍历整个 dp 数组，找到最大值即为最长公共子串的长度。

代码实现

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);string s1, s2;cin >> s1 >> s2;int res = 0;vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, 0));for (int i = 1; i <= s1.size(); i++) {for (int j = 1; j <= s2.size(); j++) {if (s1[i - 1] == s2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;res = max(res, dp[i][j]);}}}cout << res << endl;return 0;
}