首页 > 代码库 > LCS问题
LCS问题
最长公共子序列问题
核心代码:
for(int i=1;i<=len1;i++)for(int j=1;j<=len2;j++){ if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}
UVA10405 Longest Common Subsequence
模板题
代码:
#include<iostream>#include<vector>#include<cstdio>#include<cstring>#include<map>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define LL long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x)) #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 typedef pair<int,int> P;const double eps=1e-9;const int maxn=200100;const int mod=1e9+7;const int INF=1e9;char s1[1050],s2[1050];int dp[1050][1050];int main(){ while(gets(s1)&&gets(s2)) { int len1=strlen(s1); int len2=strlen(s2); CLR(dp); for(int i=1;i<=len1;i++) for(int j=1;j<=len2;j++) { if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } printf("%d\n",dp[len1][len2]); } return 0;}
UVA10252 Common Permutation
求一个最长子序列。使得子序列的全排列中有一个(可以不相同)是2个字符串的子序列.
仔细思考并不是LCS问题，直接模拟有多少个字符相同即可
代码:
#include<iostream>#include<vector>#include<cstdio>#include<cstring>#include<map>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define LL long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x)) #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 typedef pair<int,int> P;const double eps=1e-9;const int maxn=200100;const int mod=1e9+7;const int INF=1e9;char s1[1050],s2[1050];map<int,int> m,m2;int num[30];int main(){ while(gets(s1)&&gets(s2)) { m.clear();m2.clear(); int len1=strlen(s1); int len2=strlen(s2); for(int i=0;i<len1;i++) m[s1[i]-‘a‘]++; for(int i=0;i<len2;i++) m2[s2[i]-‘a‘]++; for(int i=0;i<26;i++) { num[i]=min(m[i],m2[i]); for(int j=0;j<num[i];j++) printf("%c",‘a‘+i); } printf("\n"); } return 0;}
UVA 531 Compromise
LCS问题+路径输出
路径输出标记每个位置的转移过程，然后递归输出
代码:
#include<iostream>#include<vector>#include<cstdio>#include<cstring>#include<map>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define LL long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x)) #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 typedef pair<int,int> P;const double eps=1e-9;const int maxn=105;const int mod=1e9+7;const int INF=1e9;int dp[maxn][maxn];int flag[maxn][maxn];int l1,l2;string s1[maxn],s2[maxn];void print_path(int x,int y){ if(x==0||y==0) return; if(flag[x][y]) { print_path(x-1,y-1); cout<<s1[x-1]; if(dp[x][y]!=dp[l1][l2]) cout<<" "; } else if(dp[x][y]==dp[x-1][y]) print_path(x-1,y); else print_path(x,y-1);}int main(){ l1=l2=0; while(cin>>s1[l1++]){ while(cin>>s1[l1]&&s1[l1]!="#") l1++; while(cin>>s2[l2]&&s2[l2]!="#") l2++; CLR(dp);CLR(flag); for(int i=1;i<=l1;i++) for(int j=1;j<=l2;j++) { if(s1[i-1]==s2[j-1]) { dp[i][j]=dp[i-1][j-1]+1; flag[i][j]=1; } else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } print_path(l1,l2); cout<<endl; l1=l2=0; } return 0;}
UVA10723 Cyborg Genes
LCS变种问题
仔细分析发现:最短目标字符串等于两个字符串长度的和减去最长公共子序列。dp[i][j]表示
那么数目的求和就等于最长公共子序列的路径组合数目。num[i][j]表示
首先初始化 num[0][i]=num[i][0]=1
1.s1[i]==s1[j] num[i][j]=num[i-1][j-1]
2.dp[i-1][j]>dp[i][j-1] num[i][j]=num[i-1][j]
3.dp[i-1][j]<dp[i][j-1] num[i][j]=num[i][j-1]
4.dp[i-1][j]==dp[i][j-1] num[i][j]=num[i-1][j]+num[i][j-1]
代码
#include<iostream>#include<vector>#include<cstdio>#include<cstring>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define LL long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x)) #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 typedef pair<int,int> P;const double eps=1e-9;const int maxn=200100;const int mod=1e9+7;const int INF=1e9;int dp[50][50],num[50][50],len1,len2;char s1[50],s2[50];int main(){ int n,Case=1; scanf("%d",&n); getchar(); while(n--) { gets(s1);gets(s2); int len1=strlen(s1),len2=strlen(s2); CLR(dp);CLR(num); for(int i=0;i<50;i++) num[i][0]=num[0][i]=1; for(int i=1;i<=len1;i++) for(int j=1;j<=len2;j++) { if(s1[i-1]==s2[j-1]) { dp[i][j]=dp[i-1][j-1]+1; num[i][j]=num[i-1][j-1]; } else if(dp[i-1][j]>dp[i][j-1]) { dp[i][j]=dp[i-1][j]; num[i][j]=num[i-1][j]; } else if(dp[i-1][j]<dp[i][j-1]) { dp[i][j]=dp[i][j-1]; num[i][j]=num[i][j-1]; } else { dp[i][j]=dp[i][j-1]; num[i][j]=num[i][j-1]+num[i-1][j]; } } printf("Case #%d:",Case++); printf(" %d %d\n",len1+len2-dp[len1][len2],num[len1][len2]); }}
LCS问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。