最长公共子串的长度 描述:给定两个字符串str1和str2,输出两个字符串的最长公共子串的长度(假设str1和str2的最长公共子串存在且唯一)。
时间: 2024-01-07 14:47:53 浏览: 54
可以使用动态规划来解决这个问题。定义一个二维数组dp,其中dp[i][j]表示以str1[i-1]和str2[j-1]为结尾的最长公共子串的长度。则有以下状态转移方程:
dp[i][j] = 0 (如果i=0或j=0)
dp[i][j] = dp[i-1][j-1] + 1 (如果str1[i-1] = str2[j-1])
dp[i][j] = 0 (如果str1[i-1] != str2[j-1])
最终,最长公共子串的长度即为dp数组中的最大值。具体实现如下:
```
int longestCommonSubstring(string str1, string str2) {
int m = str1.length(), n = str2.length();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
int ans = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (str1[i-1] == str2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
ans = max(ans, dp[i][j]);
} else {
dp[i][j] = 0;
}
}
}
return ans;
}
```
阅读全文