题目传送门:POJ 1934 Trip
题意:
求两个序列的最长公共子序列(LCS),LCS可能不唯一,按字典序输出所有LCS。
思路:
先按动态规划的思路,定义 数组a1~ai 与 数组b1~bi 的最长公共子序列长度为$dp[i][j]$,则有:
$$
dp[i][j]= \begin{cases} dp[i-1][j-1]+1, & \text {if($a[i]==a[j]$) } \max(dp[i-1][j],dp[i][j-1]), & \text{else} \end{cases}
$$
然后根据dp值,递归倒序求出LCS,代码如下(会超时):
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <set>
#include <algorithm>
using namespace std;
const int N=110;
set<string>ans;
char a[N],b[N];
int n,m,dp[N][N];
void get_LCS(int i,int j,string s)
// i为数组a下标,j为数组b下标,s为当前搜索到的公共子序列(逆序)
{
if(i==0||j==0)
{
ans.insert(s.assign(s.rbegin(),s.rend()));
return;
}
if(a[i]==b[j])
{
get_LCS(i-1,j-1,s+a[i]);
}
else
{
if(dp[i][j]==dp[i-1][j])
{
get_LCS(i-1,j,s);
}
if(dp[i][j]==dp[i][j-1])
{
get_LCS(i,j-1,s);
}
}
}
void get_dp()
{
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i]==b[j])dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>a+1>>b+1;
n=strlen(a+1);
m=strlen(b+1);
get_dp();
get_LCS(n,m,"");
for(set<string>::iterator it=ans.begin();it!=ans.end();it++)
printf("%s\n",(*it).c_str());
return 0;
}
Comments | NOTHING