題干：

描述

?

編寫一個程序，求兩個字符串的最長公共子串。輸出兩個字符串的長度，輸出他們的最長公共子串及子串長度。如果有多個最長公共子串請輸出在第一個字符串中先出現(xiàn)的那一個。

特別注意公共子串中可能包含有空格，但不計回車符！

輸入

兩個字符串，回車結(jié)尾，每個字符串中都可能含有空格（每個字符串的長度不超過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

來源

QDU

?

解題報告：

? ? 剛開始寫成了最長公共子序列了、、、對于從0開始讀入的字符串問題(即cin>>s而非cin>>s+1)，還調(diào)試了老半天。。結(jié)果發(fā)現(xiàn)題目要求公共子序列。。。數(shù)據(jù)量不大才兩百個字符，果斷從高往低枚舉就好了。。。如果字符數(shù)多了可以二分加速一下。、

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]; //string s1,s2; int dp[5500][5500]; int main() {cin.getline(s1+1,1004);cin.getline(s2+1,1004);int len1 = strlen(s1+1);int len2 = strlen(s2+1); // if(s1[0] == s2[0]) dp[0][0] = 1,dp[1][0] = 1,dp[0][1] = 1; // if(s1[1] == s2[0]) dp[1][0] = 1; // if(s1[0] == s2[1]) dp[0][1] = 1; // for(int i = 1; i<=len1; i++) { // for(int j = 1; j<=len2; j++) { // if(s1[i] == s2[j]) dp[i][j] = dp[i-1][j-1]+1; // else dp[i][j] = max(dp[i][j-1],dp[i-1][j]); // } // } // int ans = dp[len1][len2];//printf("ans = %d\n",ans);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 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【qduoj - 夏季学期创新题】最长公共子串（水题暴力枚举，不是LCS啊）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。