?
時間限制：
3000
ms ?|? 內(nèi)存限制：
65535
KB
難度：
3
?
- 描述
-
咱們就不拐彎抹角了，如題，需要你做的就是寫一個程序，得出最長公共子序列。
tip：最長公共子序列也稱作最長公共子串(不要求連續(xù))，英文縮寫為LCS（Longest Common Subsequence）。其定義是，一個序列 S ，如果分別是兩個或多個已知序列的子序列，且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列。
?
- 輸入
-
第一行給出一個整數(shù)N(0<N<100)表示待測數(shù)據(jù)組數(shù)
接下來每組數(shù)據(jù)兩行，分別為待測的兩組字符串。每個字符串長度不大于1000. - 輸出
- 每組測試數(shù)據(jù)輸出一個整數(shù)，表示最長公共子序列長度。每組結(jié)果占一行。
- 樣例輸入
-
2 asdf adfsd 123abc abc123abc - 樣例輸出
-
3 6
View Code
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #define max(a,b) (a>b? a:b)
5 #define Max 1010
6 using namespace std;
7 char ch1[Max],ch2[Max];
8 int d[Max][Max];
9 int dp( int i, int j)
10 {
11 int ans= 0 ;
12 if (i< 0 ||j< 0 )
13 return 0 ;
14 if (d[i][j]!=- 1 )
15 return d[i][j];
16 if (ch1[i]==ch2[j])
17 ans=dp(i- 1 ,j- 1 )+ 1 ;
18 else
19 ans=max(dp(i- 1 ,j),dp(i,j- 1 ));
20 return d[i][j]=ans;
21 }
22 int main()
23 {
24 int t,n,m;
25 cin>>t;
26 while (t--)
27 {
28 memset(d,- 1 , sizeof (d));
29 scanf( " %s%s " ,ch1,ch2);
30 n=strlen(ch1);m=strlen(ch2);
31 cout<<dp(n- 1 ,m- 1 )<<endl;
32 }
33 return 0 ;
34 }
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
