输入两个字符串,要求输出最长的公共子串。
时间: 2023-10-09 10:09:39 浏览: 69
好的,您可以使用动态规划的思想来解决这个问题。定义一个二维数组dp[i][j]表示以第一个字符串中第i个字符和第二个字符串中第j个字符结尾的最长子串的长度。则有如下状态转移方程:
如果第一个字符串中第i个字符和第二个字符串中第j个字符相等,则dp[i][j]=dp[i-1][j-1]+1。
如果第一个字符串中第i个字符和第二个字符串中第j个字符不相等,则dp[i][j]=0。
最后遍历二维数组dp,找到其中最大的值,即为最长公共子串的长度。同时通过找到最大值时的i和j,可以确定最长公共子串的具体内容。
需要注意的是,这种方法的时间复杂度是O(mn),其中m和n分别为两个字符串的长度。如果想要进一步优化算法,可以使用后缀数组(suffix array)等高级数据结构。
相关问题
输入2个字符串,要求输出最长的公共子串c语言
最长的公共子串可以通过动态规划的方法来实现。我们可以定义一个二维数组dp[m][n],其中m和n分别表示字符串1和字符串2的长度。
首先,我们需要初始化第一行和第一列。如果字符串1的第i个字符和字符串2的第j个字符相同,就将dp[i][j]设为1,否则设为0。
然后,我们可以遍历整个二维数组,通过比较字符串1的第i个字符和字符串2的第j个字符是否相同,从而进行状态转移。如果相同,就将dp[i][j]设为dp[i-1][j-1]+1,表示以字符串1的第i个字符和字符串2的第j个字符结尾的最长公共子串的长度。
遍历结束后,我们可以找到最长的公共子串的长度。要找到具体的最长公共子串,我们可以记录最长公共子串的长度对应的索引位置,然后通过字符串切片的方法获取最长公共子串。
下面是该算法的示例代码:
```c
#include <stdio.h>
#include <string.h>
void findLongestCommonSubstring(char* str1, char* str2)
{
int len1 = strlen(str1);
int len2 = strlen(str2);
int dp[len1+1][len2+1];
int max_len = 0;
int end_index = 0;
// 初始化第一行和第一列
for(int i = 0; i <= len1; i++)
dp[i][0] = 0;
for(int j = 0; j <= len2; j++)
dp[0][j] = 0;
// 动态规划求解
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_index = i - 1;
}
}
else
dp[i][j] = 0;
}
}
// 获取最长公共子串
char longest_substr[max_len+1];
strncpy(longest_substr, &str1[end_index-max_len+1], max_len);
longest_substr[max_len] = '\0';
printf("最长的公共子串为:%s\n", longest_substr);
}
int main()
{
char str1[100];
char str2[100];
printf("请输入字符串1:");
scanf("%s", str1);
printf("请输入字符串2:");
scanf("%s", str2);
findLongestCommonSubstring(str1, str2);
return 0;
}
```
以上代码中,我们定义了一个函数`findLongestCommonSubstring`来实现计算最长公共子串的功能。在`main`函数中,我们分别输入两个字符串,并调用`findLongestCommonSubstring`函数来输出最长公共子串。
C语言输入2个字符,要求输出最长的公共子串
以下是使用暴力法(Brute-Force)求解最长公共子串的C语言代码:
```c
#include <stdio.h>
#include <string.h>
int main() {
char str1[100], str2[100];
printf("请输入两个字符串:\n");
scanf("%s%s", str1, str2);
int len1 = strlen(str1), len2 = strlen(str2);
int max_len = 0, max_i = -1, max_j = -1;
for (int i = 0; i < len1; i++) {
for (int j = 0; j < len2; j++) {
int k = 0;
while (str1[i+k] == str2[j+k] && i+k < len1 && j+k < len2) {
k++;
}
if (k > max_len) {
max_len = k;
max_i = i;
max_j = j;
}
}
}
if (max_len == 0) {
printf("没有公共子串。\n");
} else {
printf("最长公共子串为:");
for (int i = 0; i < max_len; i++) {
printf("%c", str1[max_i+i]);
}
printf("\n");
}
return 0;
}
```
这里使用两层循环枚举所有可能的子串,然后再用一个while循环找到最长的公共子串。时间复杂度为O(n^3),对于较长的字符串会比较慢。
如果需要更快的算法,可以考虑使用动态规划(Dynamic Programming)或后缀数组(Suffix Array)等方法。