输入两个字符串,要求输出最长的公共子串。
时间: 2023-10-09 22:09:39 浏览: 39
好的,关于你的第一个问题,你可以使用动态规划的方法解决,具体步骤如下:
1. 定义一个二维数组 dp,dp[i][j] 表示以第一个字符串的第 i 个字符和第二个字符串的第 j 个字符为结尾的公共子串的长度。
2. 初始化 dp,即当 i=0 或 j=0 时,dp[i][j] 的值为 0,表示以两个字符串中其中一个为空串结尾的公共子串的长度为 0。
3. 对于其余的位置,如果 s1[i] == s2[j],那么 dp[i][j] 的值就是 dp[i-1][j-1]+1,即前面的最长公共子串长度加上当前字符相同的情况。如果 s1[i] != s2[j],那么 dp[i][j]=0,因为最长公共子串必须以两个字符串的任意一个字符结尾。
4. 在 dp 数组中找到最大的值,即为最长公共子串的长度。
5. 找到最长公共子串的长度后,再根据其在两个字符串中的位置,即可输出最长公共子串。
希望这个方法可以帮助你解决问题。
相关问题
输入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)等方法。