HDU 1503 LCS 最长公共子串

本文主要是介绍HDU 1503 LCS 最长公共子串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

//
//  main.cpp
//  HDU 1503 LCS 最长公共子串
//
//  Created by 郑喆君 on 8/11/14.
//  Copyright (c) 2014 itcast. All rights reserved.
//#include<cstdio>
#include<cstring>
#include<iostream>
#include<iomanip>
#include<queue>
#include<cmath>
#include<stack>
#include<map>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
typedef long long LL;
const int int_max = 0x07777777;
const int int_min = 0x80000000;
char a[110],b[110];
int dp[110][110];
int main(int argc, const char * argv[])
{while (scanf("%s %s", a, b)!=EOF) {memset(dp, 0, sizeof(dp));int lena = strlen(a);int lenb = strlen(b);dp[0][0] = (a[0]==b[0] ? 1 : 0);for(int i = 1; i < lenb; i++){if(a[0]==b[i]) dp[0][i] = 1;else dp[0][i] = dp[0][i-1];}for(int i = 1; i < lena; i++){if(b[0]==a[i]) dp[i][0] = 1;else dp[i][0] = dp[i-1][0];}for(int i = 1; i < lena; i++){for(int j = 1; j < lenb; j++){if(a[i]==b[j]) dp[i][j] = dp[i-1][j-1] + 1;else dp[i][j] = (dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]);}}char ret[250];int cnt = 0;int i = lena-1,j = lenb-1;while (i>=0 && j >= 0) {if(a[i]==b[j]){ret[cnt++] = a[i];i--;j--;}else{if(i==0) {ret[cnt++] = b[j];j--;continue;}if(j==0){ret[cnt++] = a[i];i--;continue;}if(dp[i-1][j] >= dp[i][j-1]) {ret[cnt++] = a[i];i--;}else{ret[cnt++] = b[j];j--;}}}if(i < 0){for(int u = j; u >=0; u--) ret[cnt++] = b[u];}if(j < 0){for(int u = i; u >=0; u--) ret[cnt++] = a[u];}for(int u = cnt-1; u >=0; u--) printf("%c", ret[u]);printf("\n");}
}

这篇关于HDU 1503 LCS 最长公共子串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---