題干：

描述

?

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

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

輸入

兩個字符串，回車結尾，每個字符串中都可能含有空格（每個字符串的長度不超過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來著，后來發現讀錯題了。

總結

以上是生活随笔為你收集整理的【qduoj】最长公共子串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。