题干：
描述
编写一个程序，求两个字符串的最长公共子串。输出两个字符串的长度，输出他们的最长公共子串及子串长度。如果有多个最长公共子串请输出在第一个字符串中先出现的那一个。
特别注意公共子串中可能包含有空格，但不计回车符！
输入
两个字符串，回车结尾，每个字符串中都可能含有空格（每个字符串的长度不超过200个字符)
输出
一共有四行，前两行以Length of String1:和Length of String2:开始冒号后面分别输出两字符串的长度。 第三行Maxsubstring:输出符合题目里描述的子串。第四行是Length of Maxsubstring:加子串长度。注意！冒号后面不要输出多余的空格！
输入样例 1
this is a string my string is abc
输出样例 1
Length of String1:16 Length of String2:16 Maxsubstring: string Length of Maxsubstring:7
输入样例 2
abcdef defabc
输出样例 2
Length of String1:6 Length of String2:6 Maxsubstring:abc Length of Maxsubstring:3
输入样例 3
aabbcc aabbcc
输出样例 3
Length of String1:6 Length of String2:6 Maxsubstring:aabbcc Length of Maxsubstring:6
解题报告：
这题做法很多，好像直接n^2暴力判断也可以水过，就是从s1字符串的每一个字符当成首字符，看最长能延伸到哪里（也就是跟s2最长匹配到哪里），这里要注意跟s2找到第一个不匹配的字符(假设是ss字符)的时候记录下tmplen，但是不能直接break，需要继续搜后面的s2，因为有可能还有长度tmplen2 > 刚刚记录的tmplen。这里搜的时候需要从ss开始搜也可以过，但是其实应该是从上一个第一个匹配的字符的下一个字符 开始搜。也许是数据出水了吧。总之代码比较冗长，何不试试更好想的方法？
直接枚举这个长度，从len1开始倒着枚举内层循环正着遍历（因为题目要求输出最长的最靠前的），然后每一次枚举都判断是否s1和s2中有匹配的，如果有那就直接break掉并且输出即可。
下面上法2的代码：
AC代码：
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<cmath>
#include<map>
#include<iostream>
#include<algorithm>
#define ll long long
const ll mod = 1e9+7;
using namespace std;
char s1[5005],s2[5005],tmp[5005];
int main()
{
cin.getline(s1+1,1004);
cin.getline(s2+1,1004);
int len1 = strlen(s1+1);
int len2 = strlen(s2+1);
int ans,flag = 0;
for(ans = len1; ans >=0; ans--) {
for(int i = 1; i<=len1-ans+1; i++) {
for(int j = 0; j<ans; j++) tmp[j] = s1[i+j];
tmp[ans] = '\0';
//printf("tmp=%s\n",tmp);
if(strstr(s2+1,tmp) != NULL) {
flag = 1;
break;
}
}
if(flag) break;
}
printf("Length of String1:%d\n",len1);
printf("Length of String2:%d\n",len2);
printf("Maxsubstring:%s\n",tmp);
printf("Length of Maxsubstring:%d\n",ans);
return 0 ;
}
总结：
ps刚开始这题写错了WA3次，因为看成了公共子序列问题了，，，想dp来着，后来发现读错题了。
京公网安备 11010502036488号