华为机考题：查找两个字符串a,b中的最长公共子串

题目描述查找两个字符串a、b中的最长公共子串。若有多个输出在较短串中最先出现的那个。注子串的定义为字符串中连续的一段。输入描述输入两个字符串。输出描述返回重复出现的字符。示例输入textabcdefghijklmnop abcsafjklmnopqrstuvw输出textjklmnopC 语言解决方案思路这是一道经典的动态规划题。设dp[i][j]表示以a[i-1]和b[j-1]结尾的公共子串长度。若a[i-1] b[j-1]则dp[i][j] dp[i-1][j-1] 1。否则dp[i][j] 0。过程中记录最大值及结束位置最后截取子串输出。注意题目要求若有多个输出在较短串中最先出现的那个所以我们让a始终是较短的那个串并且只在新长度严格大于当前最大值时更新保证最先出现。代码实现c#include stdio.h #include string.h int main(void) { char a[1005], b[1005]; scanf(%s, a); scanf(%s, b); int la strlen(a), lb strlen(b); // 保证 a 是较短的串符合较短串中最先出现的要求 if (la lb) { char tmp[1005]; strcpy(tmp, a); strcpy(a, b); strcpy(b, tmp); int t la; la lb; lb t; } int dp[1005][1005]; memset(dp, 0, sizeof(dp)); int maxLen 0, endPos 0; // endPos 记录最长子串在 a 中的结束下标 for (int i 1; i la; i) { for (int j 1; j lb; j) { if (a[i - 1] b[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; // 严格大于才更新保证最先出现 if (dp[i][j] maxLen) { maxLen dp[i][j]; endPos i - 1; } } } } // 输出最长公共子串 for (int k endPos - maxLen 1; k endPos; k) { putchar(a[k]); } putchar(\n); return 0; }