网站流量指数,合浦建设局网站,网站js时间代码,全网客源app题干#xff1a;
描述 编写一个程序#xff0c;求两个字符串的最长公共子串。输出两个字符串的长度#xff0c;输出他们的最长公共子串及子串长度。如果有多个最长公共子串请输出在第一个字符串中先出现的那一个。
特别注意公共子串中可能包含有空格#xff0c;但不计回车…题干
描述 编写一个程序求两个字符串的最长公共子串。输出两个字符串的长度输出他们的最长公共子串及子串长度。如果有多个最长公共子串请输出在第一个字符串中先出现的那一个。
特别注意公共子串中可能包含有空格但不计回车符
输入
两个字符串回车结尾每个字符串中都可能含有空格每个字符串的长度不超过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代码
#includecstdio
#includequeue
#includestring
#includecstring
#includecmath
#includemap
#includeiostream
#includealgorithm
#define ll long long
const ll mod 1e97;
using namespace std;
char s1[5005],s2[5005],tmp[5005];
int main()
{cin.getline(s11,1004);cin.getline(s21,1004);int len1 strlen(s11);int len2 strlen(s21);int ans,flag 0;for(ans len1; ans 0; ans--) {for(int i 1; ilen1-ans1; i) {for(int j 0; jans; j) tmp[j] s1[ij];tmp[ans] \0;//printf(tmp%s\n,tmp);if(strstr(s21,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来着后来发现读错题了。
