最长公共子序列【东北大学oj数据结构10-3】C++

题面

对于给定两个序列 X 和 Y , 序列 Z 是 X 和 Y 的公共子序列是指假如 Z 同时是 X 和 Y 的子序列。
例如：假如 X = {a, b, c, b, d, a, b} 和 Y = {b, d, c, a, b, a} ,
那么序列 {b, c, a} 是 X 和 Y 的一个公共子序列。
但是序列 { b , c, a } 不是 X 和 Y 的最长公共子序列(LCS) , 由于它的长度是3。
而序列 {b,c,b,a} ( X 和 Y 都有这个序列)的长度是 4, 又没有长度大于或即是 5 的公共子序列，所以序列 {b,c,b,a} 是 X 和 Y 的最长公共子序列。
编写一个程序，找出给定的两个序列 X 和 Y 的LCS的长度。
输入

输入由多个数据集组成。
在第一行中，给出了一个整数 q，它是数据集的数量。
在下面的 2 × q 行中，给出了由两个序列 X 和 Y 组成的每个数据集。
输出

对于每个数据集，在一行中打印 X 和 Y 的 LCS 长度。
约束

1≤q≤150
1≤X和Y的长度≤1000
假如数据集包含长度大于100的序列，则Q≤20
输入样例

   3
abcbdab
bdcaba
abc
abc
abc
bc
  输出样例

   4
3
2 
  代码

 

1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
4. #include <string>
6. using namespace std;
8. int main() {
9.     int n;
10.     cin >> n;
11.     for(int i=0;i<n;i++)
12.     {
13.         string a;
14.         string b;
15.         cin>>a>>b;
16.         int x=a.size();
17.         int y=b.size();
18.         vector<vector<int> > dq(x+1,vector<int>(y+1,0));
19.         for(int j=0;j<x;j++)
20.         {
21.             for(int k=0;k<y;k++)
22.             {
23.                 if(a[j]==b[k])
24.                 {
25.                     dq[j+1][k+1]=dq[j][k]+1;
26.                 }
27.                 else
28.                 {
29.                     dq[j+1][k+1]=max(dq[j+1][k],dq[j][k+1]);
30.                 }
31.             }
32.         }
33.         cout<<dq[x][y]<<endl;
34.     }
35.     return 0;
36. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。