Problem Description

從一個給定的串中刪去（不一定連續地刪去）0個或0個以上的字符，剩下地字符按原來順序組成的串。例如：“ ”，“a”，“xb”，“aaa”，“bbb”，“xabb”，“xaaabbb”都是串“xaaabbb”的子串。（例子中的串不包含引號。）
?
編程求N個非空串的最長公共子串的長度。限制：2<=N<=100；N個串中的字符只會是數字0，1，…，9或小寫英文字母a，b，…，z；每個串非空且最多含100個字符；N個串的長度的乘積不會超過30000。

Input

文件第1行是一個整數T，表示測試數據的個數（1<=T<=10）。接下來有T組測試數據。各組測試數據的第1行是一個整數Ni，表示第i組數據中串的個數。各組測試數據的第2到N+1行中，每行一個串，串中不會有空格，但行首和行末可能有空格，這些空格當然不算作串的一部分。

Output

輸出T行，每行一個數，第i行的數表示第i組測試數據中Ni個非空串的最長公共子串的長度。

Example Input

1 3 ab bc cd

Example Output

0

求解最長公共子串問題利用動態規劃思想，不管是否理解動態規劃，把這個原理弄明白就行。

首先直接給出一個例子：

主串：str[7]=”ABCBDAB”?

子串：substr[6]=”BDCABA”

求最長公共子串？

我們先不考慮如何實現這個先來分析這個結果為多少，通過比較容易得出當子串為BDAB時候最長公共子串的值為4。

好了現在我們一起來分析算法了！

首先定義一個sum[][]二維數組初始化為0，行表示主串的字符，列表示子串的字符，那么sum[i][j表示主串的第i(從一開始數)個字符與子串的j+1個字符的最長公共子串的結果值，最后sum[7][6]的值就是最長公共子串的結果。

首先主串中的A與子串匹配，當子串數組的下標為3、5時候匹配，首先分析3，當下標3與其主串的首字符匹配，那么此時sum[1][4]=1,此時的sum[1][5]=sum[1][6]=1(注意，因為匹配到這里的時候最長公共子串仍然為1) 主串繼續匹配，str[0]=substr[5]此時sum[2][6]=1，主串往后移動，str[1]=substr[0] 則sum[2][x]=1（x>=1）,,繼續移動，str[2]=str[2]此時sum[3][3]=sum[2][2]+1=2后面一以此類推...

#include<iostream> #include<stdio.h> #include<algorithm> #include<cstring> using namespace std; int main() {char x[505],y[505];int sum[505][505],i,j,len1,len2;while(gets(x)){gets(y);len1=strlen(x);len2=strlen(y);memset(sum,0,sizeof(sum));for(i=1;i<=len1;i++){for(j=1;j<=len2;j++){if(x[i-1]==y[j-1])sum[i][j]=sum[i-1][j-1]+1;elsesum[i][j]=max(sum[i-1][j],sum[i][j-1]);}}printf("%d\n",sum[len1][len2]);}return 0; }/*超時作法 #include<iostream> #include<stdio.h> #include<algorithm> #include<cstring> using namespace std;int main() {while(1){ char str[500],substr[500];int a[500]={0},b[500]={0};gets(str);gets(substr);for(int i=0;i<strlen(substr);i++){for(int j=0;j<strlen(str);j++){if(str[j]==substr[i]){a[j]=1;//標記 b[j]=1;}}}for(int i=1;i<strlen(str);i++){for(int j=0;j<i;j++){if(str[i]>str[j]&&(a[i])&&(a[j])&&b[i]<b[j]+1){b[i]=b[j]+1;}}} int ans=-1;for(int i=0;i<strlen(str);i++){if(ans<b[i])ans=b[i];}cout<<ans<<endl;}return 0; }*/

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

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

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