HDU 1503

• 题意: 给出2个字符串,求出 最短的包含该两个字符串 的字符串
• 2个字符串的公共部分只出现一次,求LCS串时其他的点顺带累加到串中,
• 注意 i , j 代表的是 a[]还是b[] 就行

  #include <iostream>
  #include <string.h>
  #include <string>
  #include <vector>
  #include <algorithm>
  
  using namespace std;
  
  const int maxn = 1e3+10;
  
  int dp[maxn][maxn];
  char a[maxn];
  char b[maxn];
  
  void lcs() {
  	memset(dp,0,sizeof dp);
  	int alen = strlen(a+1);
  	int blen = strlen(b+1);
  
  	//确定dp的范围条件 
  	
  	dp[alen][0] = 0; //a全都有,b为空
  	dp[0][blen] = 0; //b全都有,a为空
  
  	
  
  	for (int i=1; i<=alen; i++) {
  		for (int j=1; j<=blen; 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]);
  		}
  	}
  }
  
  void stringlcs(int alen,int blen) { //根据打出来的表 来求 公共串
  	string ans;
  	int i = alen;
  	int j = blen;
  
  	while (dp[i][j]) {
  		if (a[i] == b[j]) {
  			ans += a[i--];
  			j--;
  		}
  		else if (dp[i][j-1] < dp[i-1][j]) {
  			ans += a[i--];
  		}
  		else if (dp[i][j-1] >= dp[i-1][j]) {
  			ans += b[j--];
  		}
  	}
  	while ( i!=0 ) ans += a[i--];
  	while ( j!=0 ) ans += b[j--]; 
  	reverse(ans.begin(),ans.end());
  //	printf("%s\n",ans);
  	cout << ans << endl;
  }
  
  int main() {
  //	freopen("a.txt","r",stdin);
  	while (scanf("%s",a+1) != EOF && scanf("%s",b+1) != EOF) {
  		lcs();
  		int alen = strlen(a+1);
  		int blen = strlen(b+1);
  		stringlcs(alen,blen);
  	}
  	return 0;
  }