小明有两个字符串,他想找出其中最长的公共连续子串的长度,希望你能帮助他。例如,两个字符串分别为“abcde”和“abdge”,结果为2。c语言表示
时间: 2023-08-31 15:27:26 浏览: 75
### 回答1:
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
char s1[100], s2[100];
int len1, len2, dp[101][101], ans = 0;
scanf("%s%s", s1, s2);
len1 = strlen(s1);
len2 = strlen(s2);
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
ans = max(ans, dp[i][j]);
}
}
}
printf("%d\n", ans);
return 0;
}
### 回答2:
题目要求我们给定两个字符串,找出它们之间最长的公共连续子串的长度,并用C语言实现。
我们可以使用动态规划的方法解决这个问题。首先,定义一个二维数组dp[m][n],其中m和n分别表示两个字符串的长度。数组dp[i][j]表示以第一个字符串的第i个字符和第二个字符串的第j个字符作为结尾的公共连续子串的长度。
然后,我们遍历两个字符串的每个字符,如果当前字符相等,我们设置dp[i][j] = dp[i-1][j-1] + 1,表示以当前字符结尾的公共连续子串的长度是前一个字符结尾的公共连续子串的长度加1。如果当前字符不相等,即第一个字符串的第i个字符和第二个字符串的第j个字符不相等,那么dp[i][j]就是0,表示当前没有公共连续子串。
在遍历过程中,我们记录下最大的dp[i][j]值,即为两个字符串之间最长的公共连续子串的长度。
最后,我们返回最大的dp[i][j]值,即为结果。
下面是C语言的实现代码:
```c
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int findLongestCommonSubstring(char* str1, char* str2) {
int len1 = strlen(str1);
int len2 = strlen(str2);
int dp[len1 + 1][len2 + 1];
int maxLen = 0;
memset(dp, 0, sizeof(dp));
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;
maxLen = max(maxLen, dp[i][j]);
}
}
}
return maxLen;
}
int main() {
char str1[100], str2[100];
printf("请输入两个字符串:\n");
scanf("%s %s", str1, str2);
int result = findLongestCommonSubstring(str1, str2);
printf("最长公共连续子串长度为:%d\n", result);
return 0;
}
```
以上是使用C语言解决该问题的代码,通过动态规划的方法,我们可以找到两个字符串之间最长的公共连续子串的长度。
### 回答3:
可以使用动态规划的方法来解决这个问题。
我们可以定义一个二维数组dp,其中dp[i][j]表示以字符串1的第i个字符和字符串2的第j个字符结尾的最长公共连续子串的长度。
首先,我们需要初始化dp数组。当i=0或者j=0时,dp[i][j]的值应该为0,因为此时没有字符可以来构成公共连续子串。
然后,我们需要遍历字符串1和字符串2的每个字符,当字符串1的第i个字符等于字符串2的第j个字符时,说明找到了一个公共字符,我们可以更新dp[i][j]的值为dp[i-1][j-1]+1,表示在原来的公共连续子串基础上加上这一个字符。
遍历过程中,我们还需要记录公共连续子串的最长长度,即时时更新的dp[i][j]的值。
最后,遍历结束后,我们就可以得到最长公共连续子串的长度,即dp数组中的最大值。
下面是使用C语言实现的代码:
```c
#include <stdio.h>
#include <string.h>
int maxCommonSubstr(char* str1, char* str2) {
int len1 = strlen(str1);
int len2 = strlen(str2);
int dp[len1+1][len2+1];
int maxLen = 0;
// 初始化dp数组
for(int i = 0; i <= len1; i++) {
for(int j = 0; j <= len2; j++) {
dp[i][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] > maxLen) {
maxLen = dp[i][j];
}
}
else {
dp[i][j] = 0;
}
}
}
return maxLen;
}
int main() {
char str1[] = "abcde";
char str2[] = "abdge";
int maxLen = maxCommonSubstr(str1, str2);
printf("最长公共连续子串的长度为:%d\n", maxLen);
return 0;
}
```
输出结果为:
```
最长公共连续子串的长度为:2
```
即符合题目要求的结果。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)