[已解决]有没有大佬帮忙解释一下为什么是这样

wsccp

#include <stdio.h>
#include <string.h>
#include <ctype.h>

void findCommonSubstring(const char *str1, const char *str2) {
        int len1 = strlen(str1);
        int len2 = strlen(str2);

        int maxLen = 0; // 用于记录最长公共子字符串的长度
        int endIndex = 0; // 用于记录最长公共子字符串的结束索引

        // 创建一个二维数组，用于存储子问题的解
        int dp[len1 + 1][len2 + 1];

        // 初始化数组，将所有元素都设置为0
        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];
                                        endIndex = i - 1;
                                }
                        }
                }
        }

        // 输出最长公共子字符串
        if (maxLen > 0) {
                printf("最长公共子字符串: ");
                for (int i = endIndex - maxLen + 1; i <= endIndex; i++) {
                        printf("%c", str1[i]);
                }
                printf("\n");
        } else {
                printf("没有公共子字符串\n");
        }
}

int main() {
        char str1[100], str2[100];
        unsigned int i;

        printf("请输入第一个字符串（仅含字母）：");
        scanf("%s", str1);

        printf("请输入第二个字符串：");
        scanf("%s", str2);
       
        findCommonSubstring(str1, str2);

        return 0;
}

最佳答案

月排行榜 / 总排行榜

Mike_python小

2023-10-29 13:49:43

问题描述：
有人希望解释一下为什么这段C/C++代码可以找到最长公共子字符串。

2. #include <stdio.h>
3. #include <string.h>
4. #include <ctype.h>
6. void findCommonSubstring(const char *str1, const char *str2) {
7.         int len1 = strlen(str1);
8.         int len2 = strlen(str2);
10.         int maxLen = 0; // 用于记录最长公共子字符串的长度
11.         int endIndex = 0; // 用于记录最长公共子字符串的结束索引
13.         // 创建一个二维数组，用于存储子问题的解
14.         int dp[len1 + 1][len2 + 1];
16.         // 初始化数组，将所有元素都设置为0
17.         for (int i = 0; i <= len1; i++) {
18.                 for (int j = 0; j <= len2; j++) {
19.                         dp[i][j] = 0;
20.                 }
21.         }
23.         // 使用动态规划填充二维数组
24.         for (int i = 1; i <= len1; i++) {
25.                 for (int j = 1; j <= len2; j++) {
26.                         if (str1[i - 1] == str2[j - 1]) {
27.                                 dp[i][j] = dp[i - 1][j - 1] + 1;
28.                                 if (dp[i][j] > maxLen) {
29.                                         maxLen = dp[i][j];
30.                                         endIndex = i - 1;
31.                                 }
32.                         }
33.                 }
34.         }
36.         // 输出最长公共子字符串
37.         if (maxLen > 0) {
38.                 printf("最长公共子字符串: ");
39.                 for (int i = endIndex - maxLen + 1; i <= endIndex; i++) {
40.                         printf("%c", str1[i]);
41.                 }
42.                 printf("\n");
43.         } else {
44.                 printf("没有公共子字符串\n");
45.         }
46. }
48. int main() {
49.         char str1[100], str2[100];
50.         unsigned int i;
52.         printf("请输入第一个字符串（仅含字母）：");
53.         scanf("%s", str1);
55.         printf("请输入第二个字符串：");
56.         scanf("%s", str2);
58.         findCommonSubstring(str1, str2);
60.         return 0;
61. }

复制代码

请解释一下这段代码的工作原理。

解决方案：

这段代码使用动态规划算法来查找两个字符串的最长公共子字符串。以下是代码的工作原理的详细解释：

1. 首先，函数findCommonSubstring接收两个字符串str1和str2作为输入参数。

2. 程序使用strlen函数获取两个字符串的长度len1和len2。

3. 创建一个二维数组dp，大小为(len1 + 1) × (len2 + 1)，用于存储子问题的解。数组dp的每个元素dp[i][j]表示以str1[i-1]和str2[j-1]结尾的最长公共子字符串的长度。

4. 初始化数组dp，将所有元素都设置为0。

5. 使用动态规划填充二维数组dp。遍历字符串str1和str2的所有字符，如果当前字符相等（即str1[i-1] == str2[j-1]），则说明可以将当前字符加入到最长公共子字符串中，因此更新dp[i][j] = dp[i-1][j-1] + 1。

6. 在填充过程中，记录最长公共子字符串的长度maxLen和结束索引endIndex。如果当前计算得到的最长公共子字符串长度大于之前记录的maxLen，则更新maxLen和endIndex。

7. 最后，根据最长公共子字符串的长度和结束索引，输出结果。如果最长公共子字符串的长度大于0，则输出最长公共子字符串；否则，输出"没有公共子字符串"。

这个算法的时间复杂度为O(len1 × len2)，其中len1和len2分别是两个输入字符串的长度。

希望以上解释能够帮助您理解这段代码的工作原理。如果还有其他问题，请随时提问。

球一个最佳答案谢谢啦！这对我非常重要！

跳转到最佳答案楼层

isdkz

这段代码实现了一个函数 findCommonSubstring，用于查找两个字符串的最长公共子字符串。

首先，代码通过 strlen 函数获取两个字符串的长度 len1 和 len2。

然后，创建一个二维数组 dp，用于存储子问题的解。数组的大小为 (len1 + 1) * (len2 + 1)。

接下来，通过两个嵌套的循环，使用动态规划的方式填充二维数组 dp。循环变量 i 和 j 分别表示字符串 str1 和 str2 的索引。如果 str1[i - 1] 等于 str2[j - 1]，则说明当前字符是两个字符串的公共字符，将 dp[ i][j] 设置为 dp[i - 1][j - 1] + 1。同时，如果 dp[ i][j] 大于之前记录的最大长度 maxLen，则更新 maxLen 和 endIndex。

最后，根据最长公共子字符串的长度 maxLen 进行判断。如果 maxLen 大于 0，则输出最长公共子字符串。否则，输出 "没有公共子字符串"。

在主函数中，通过 scanf 函数获取用户输入的两个字符串，然后调用 findCommonSubstring 函数进行计算。

这段代码的时间复杂度为 O(len1 * len2)，空间复杂度为 O(len1 * len2)。

陶远航

这段代码的主要目标是找出两个字符串中的最长公共子字符串。这里使用了动态规划的方法来解决这个问题。下面是代码的详细解释：

1. findCommonSubstring函数接收两个字符串作为输入。

2. 首先，计算两个字符串的长度。

3. 定义两个变量maxLen和endIndex，分别用于存储最长公共子字符串的长度和结束索引。

4. 创建一个二维数组dp，其大小为(len1 + 1) x (len2 + 1)。这个数组用于存储子问题的解。这是动态规划的关键部分。

5. 初始化dp数组，将所有元素设置为0。

6. 使用两个嵌套的for循环遍历两个字符串。如果在某个位置，两个字符串的字符相同，那么dp[ i][j]就等于dp[i - 1][j - 1] + 1。这表示当前的公共子字符串长度是前一个公共子字符串长度加1。

7. 如果新计算的公共子字符串长度大于maxLen，那么更新maxLen和endIndex。

8. 最后，如果maxLen大于0，那么就输出最长公共子字符串。否则，输出\"没有公共子字符串\"。

在main函数中，首先输入两个字符串，然后调用findCommonSubstring函数找出并打印最长公共子字符串。

这个程序的关键在于动态规划的使用，通过存储和利用子问题的解，避免了重复计算，提高了效率。
请注意，本回答来自GPT-4
如果问题已经解决，请设置最佳答案

wsccp

isdkz 发表于 2023-10-29 13:47
这段代码实现了一个函数 findCommonSubstring，用于查找两个字符串的最长公共子字符串。

首先，代码通过 ...

为什么dp[len1+1][len2+1]这里要加1

Mike_python小

问题描述：
有人希望解释一下为什么这段C/C++代码可以找到最长公共子字符串。

2. #include <stdio.h>
3. #include <string.h>
4. #include <ctype.h>
6. void findCommonSubstring(const char *str1, const char *str2) {
7.         int len1 = strlen(str1);
8.         int len2 = strlen(str2);
10.         int maxLen = 0; // 用于记录最长公共子字符串的长度
11.         int endIndex = 0; // 用于记录最长公共子字符串的结束索引
13.         // 创建一个二维数组，用于存储子问题的解
14.         int dp[len1 + 1][len2 + 1];
16.         // 初始化数组，将所有元素都设置为0
17.         for (int i = 0; i <= len1; i++) {
18.                 for (int j = 0; j <= len2; j++) {
19.                         dp[i][j] = 0;
20.                 }
21.         }
23.         // 使用动态规划填充二维数组
24.         for (int i = 1; i <= len1; i++) {
25.                 for (int j = 1; j <= len2; j++) {
26.                         if (str1[i - 1] == str2[j - 1]) {
27.                                 dp[i][j] = dp[i - 1][j - 1] + 1;
28.                                 if (dp[i][j] > maxLen) {
29.                                         maxLen = dp[i][j];
30.                                         endIndex = i - 1;
31.                                 }
32.                         }
33.                 }
34.         }
36.         // 输出最长公共子字符串
37.         if (maxLen > 0) {
38.                 printf("最长公共子字符串: ");
39.                 for (int i = endIndex - maxLen + 1; i <= endIndex; i++) {
40.                         printf("%c", str1[i]);
41.                 }
42.                 printf("\n");
43.         } else {
44.                 printf("没有公共子字符串\n");
45.         }
46. }
48. int main() {
49.         char str1[100], str2[100];
50.         unsigned int i;
52.         printf("请输入第一个字符串（仅含字母）：");
53.         scanf("%s", str1);
55.         printf("请输入第二个字符串：");
56.         scanf("%s", str2);
58.         findCommonSubstring(str1, str2);
60.         return 0;
61. }

复制代码

请解释一下这段代码的工作原理。

解决方案：

这段代码使用动态规划算法来查找两个字符串的最长公共子字符串。以下是代码的工作原理的详细解释：

1. 首先，函数findCommonSubstring接收两个字符串str1和str2作为输入参数。

2. 程序使用strlen函数获取两个字符串的长度len1和len2。

3. 创建一个二维数组dp，大小为(len1 + 1) × (len2 + 1)，用于存储子问题的解。数组dp的每个元素dp[i][j]表示以str1[i-1]和str2[j-1]结尾的最长公共子字符串的长度。

4. 初始化数组dp，将所有元素都设置为0。

5. 使用动态规划填充二维数组dp。遍历字符串str1和str2的所有字符，如果当前字符相等（即str1[i-1] == str2[j-1]），则说明可以将当前字符加入到最长公共子字符串中，因此更新dp[i][j] = dp[i-1][j-1] + 1。

6. 在填充过程中，记录最长公共子字符串的长度maxLen和结束索引endIndex。如果当前计算得到的最长公共子字符串长度大于之前记录的maxLen，则更新maxLen和endIndex。

7. 最后，根据最长公共子字符串的长度和结束索引，输出结果。如果最长公共子字符串的长度大于0，则输出最长公共子字符串；否则，输出"没有公共子字符串"。

这个算法的时间复杂度为O(len1 × len2)，其中len1和len2分别是两个输入字符串的长度。

希望以上解释能够帮助您理解这段代码的工作原理。如果还有其他问题，请随时提问。

球一个最佳答案谢谢啦！这对我非常重要！

wsccp

Mike_python小 发表于 2023-10-29 13:49
问题描述：
有人希望解释一下为什么这段C/C++代码可以找到最长公共子字符串。

为什么dp[len1+1][len2+1]这里len1和len2要+1