给定两个字符串,求最长的公共子串及长度,用c++语言实现,使时间复杂度和空间复杂度尽可能小
时间: 2023-05-20 15:03:01 浏览: 59
可以使用动态规划算法来解决这个问题。具体步骤如下:
1. 定义一个二维数组dp,其中dp[i][j]表示以第一个字符串的第i个字符和第二个字符串的第j个字符结尾的最长公共子串的长度。
2. 初始化dp数组,将第一行和第一列都设为0。
3. 遍历两个字符串,如果第一个字符串的第i个字符和第二个字符串的第j个字符相等,则dp[i][j] = dp[i-1][j-1] + 1,否则dp[i][j] = 0。
4. 在遍历过程中记录最长公共子串的长度和结束位置。
5. 最后根据最长公共子串的长度和结束位置,可以得到最长公共子串。
时间复杂度为O(m*n),空间复杂度为O(m*n)。
以下是C语言实现的代码:
```c
#include <stdio.h>
#include <string.h>
#define MAX_LEN 100
int main()
{
char str1[MAX_LEN], str2[MAX_LEN];
int dp[MAX_LEN][MAX_LEN] = {0};
int len1, len2, max_len = 0, end_pos = 0;
printf("请输入第一个字符串:");
scanf("%s", str1);
printf("请输入第二个字符串:");
scanf("%s", str2);
len1 = strlen(str1);
len2 = strlen(str2);
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (str1[i-1] == str2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
if (dp[i][j] > max_len) {
max_len = dp[i][j];
end_pos = i - 1;
}
}
}
}
printf("最长公共子串为:");
for (int i = end_pos - max_len + 1; i <= end_pos; i++) {
printf("%c", str1[i]);
}
printf("\n长度为:%d\n", max_len);
return 0;
}
```