ZOJ 1953 Advanced Fruits(LCS)

題意:給出兩個字符串,求能滿足子串(可以不連續)中包含給出的兩個字符串的最短字符串.

思路:本質上就是LCS問題,做法是先找出兩個串的LCS,並記錄其位置

設dp[i][j]為Ａ串以第i個字符結尾B串以第j個字符結尾的LCS, 用path數組來記錄路徑,

如果A[i] == B[j] 那麼dp[i][j] = dp[i - 1][j - 1].

否則 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) .

用兩個數組pos1, pos2分別代表LCS在各自串中的位置.

那麼不是LCS的字符就要按照一定的順序打印,詳細的看代碼吧

#include 
#include 
#include 
#include 
using namespace std;
const int MAX = 128;

int dp[MAX][MAX];
int pos1[MAX], pos2[MAX], cnt;
char path[MAX][MAX];
char f1[MAX], f2[MAX];

void traverse(int i, int j){
	if(i == 0 || j == 0)return;
	if(path[i][j] == 0){
		traverse(i - 1, j - 1);
		pos1[cnt] = i;
		pos2[cnt++] = j;
	}else if(path[i][j] == 1){
		traverse(i - 1, j);
	}else{
		traverse(i, j - 1);
	}
}

int main(int argc, char const *argv[]){
	while(scanf("%s%s", f1 + 1, f2 + 1) == 2){
		memset(dp, 0, sizeof(dp));

		int len1 = strlen(f1 + 1), len2 = strlen(f2 + 1);
		for(int i = 1; i <= len1; ++i){
			for(int j = 1; j <= len2; ++j){
				if(f1[i] == f2[j]){
					dp[i][j] = dp[i - 1][j - 1] + 1;
					path[i][j] = 0;
				}else if(dp[i - 1][j] > dp[i][j - 1]){
					dp[i][j] = dp[i - 1][j];
					path[i][j] = 1;
				}else{
					dp[i][j] = dp[i][j - 1];
					path[i][j] = 2;
				}
			}
		}

		cnt = 1;
		traverse(len1, len2);
		pos1[cnt] = len1 + 1;
		pos2[cnt++] = len2 + 1;
		for(int i = 1; i < cnt; ++i){
			for(int j = pos1[i - 1] + 1; j < pos1[i]; ++j){
				printf("%c", f1[j]);
			}
			for(int j = pos2[i - 1] + 1; j < pos2[i]; ++j){
				printf("%c", f2[j]);
			}
			if(i != cnt - 1)
				printf("%c", f1[pos1[i]]);
		}
		printf("\n");
	}
	return 0;
}