最长公共子序列的长度和输出/HDU1159

给出两字符串,要求输出两字符串的最长公共子序列;

这里有必要解释一下子串和子序列的区别,子串要求连续,子序列不必.

也就是说,对于 "abckkkef" 和"abcef"这两字符串而言,他们最长的公共子串是"abc",而最长公共子序列是"abcef"

最长公共子序列,最长上升子序列,很显然都是动态规划的思想,不同的是,"公共"的话是要对两个序列进行处理

my code:

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
const int M = 1000;
const int N = 1000;
int lcs[M][N];
int decision[M][N];
enum
{
I_J,    //1+lcs[i+1][j+1]
I_1,    //lcs[i+1][j]
J_1     //lcs[i][j+1]
}; 
void Lcs(string A,string B)
{
int m = A.size();
int n = B.size();
//初始化 
for (int j = 0;j <= n;++j) lcs[m][j] = 0;
for (int i = 0;i <= m;++i) lcs[i][n] = 0;
//递推
for (int i = m-1;i >= 0;--i)
{
for (int j = n-1;j >= 0;--j)
{
if (A[i] == B[j])
{
lcs[i][j] = 1+lcs[i+1][j+1];
decision[i][j] = I_J;
}
else if (lcs[i][j+1] < lcs[i+1][j])
{
lcs[i][j] = lcs[i+1][j];
decision[i][j] = I_1;
}
else 
{
lcs[i][j] = lcs[i][j+1];
decision[i][j] = J_1;
}
}
} 
//输出
for (int i = 0,j = 0;i < m&&j < n;)
{
switch(decision[i][j])
{
case I_J://公共 
cout<<A[i];
++i,++j;
break;
case I_1:
++i;
break;
case J_1:
    ++j;
break; 
}
} 
cout<<endl;
}
int main()
{
string a,b;
while (cin>>a>>b)
{
Lcs(a,b);
}
return 0;
} 

HDU 1159 : 点击打开链接

ac代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int M = 1005;
const int N = 1005;
int lcs[M][N];
int decision[M][N];
enum
{
I_J,    //1+lcs[i+1][j+1]
I_1,    //lcs[i+1][j]
J_1     //lcs[i][j+1]
}; 
int Lcs(char* A,char* B)
{
int m = strlen(A);
int n = strlen(B);
//初始化 
for (int j = 0;j <= n;++j) lcs[m][j] = 0;
for (int i = 0;i <= m;++i) lcs[i][n] = 0;
//递推
for (int i = m-1;i >= 0;--i)
{
for (int j = n-1;j >= 0;--j)
{
if (A[i] == B[j])
{
lcs[i][j] = 1+lcs[i+1][j+1];
decision[i][j] = I_J;
}
else if (lcs[i][j+1] < lcs[i+1][j])
{
lcs[i][j] = lcs[i+1][j];
decision[i][j] = I_1;
}
else 
{
lcs[i][j] = lcs[i][j+1];
decision[i][j] = J_1;
}
}
} 
//输出
int ans = 0;
for (int i = 0,j = 0;i < m&&j < n;)
{
switch(decision[i][j])
{
case I_J://公共 
//cout<<A[i];
++i,++j;
++ans;
break;
case I_1:
++i;
break;
case J_1:
    ++j;
break; 
}
} 
return ans;
//cout<<endl;
}
int main()
{
char a[M];
char b[N];
while (cin>>a>>b)
{
cout<<Lcs(a,b)<<endl;
}
return 0;
}