A掉这个题我十分激动,很久没有做dp题了,因为不是很开窍,前两天,累了就趴在床上看算导,翻到动态规划,没想到很顺利地从头到尾看完了,所以就像尝试下dp….这个属于最长公共子序列,以前做过不过这个题需要记录路径,由于路径不唯一,所以是special judge,两个字符串要合并成一个,并且公共部分只输出一次,这其中的细节认真想想就可以做出来..1Y,很高兴~
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
char a[110],b[110],c[110],temp;
int dp[110][110],before[110][110][2];
int i,j,t,count;
int lena,lenb;
while( cin >> a+1 >> b+1 )
{
lena = strlen(a+1);
lenb = strlen(b+1);
memset( dp,0,sizeof(dp) );
for( i = 1; i <= lena; i++ )
for( j = 1; j <= lenb; j++ )
if( a[i] == b[j] )
{
dp[i][j] = dp[i-1][j-1] + 1;
before[i][j][0] = i - 1;
before[i][j][1] = j - 1;
}
else
{
if( dp[i-1][j] > dp[i][j-1] ){
dp[i][j] = dp[i-1][j];
before[i][j][0] = i - 1;
before[i][j][1] = j;
}
else{
dp[i][j] = dp[i][j-1];
before[i][j][0] = i;
before[i][j][1] = j - 1;
}
}
//以上是dp的过程,同时记录路径
i=lena;j=lenb;
count = 0;
while( i && j )
{
if( a[i] == b[j] )
c[count++] = a[i];
t = before[i][j][0];
j = before[i][j][1];
i = t;
}
c[count] = '\0';
for( i = 0,count--; i < count; i++,count-- )
temp=c[i],c[i]=c[count],c[count]=temp;
//以上是通过dp的路径,求出公共序列,即c(LCS)
for( i = j = 1,t = 0; c[t]!='\0' ; )
{
if( a[i] == c[t] && b[j] == c[t] )
cout<<c[t],t++,i++,j++;
else if( a[i] == c[t] )
cout<<b[j++];
else if( b[j] == c[t] )
cout<<a[i++];
else
cout<<a[i++]<<b[j++];
}
cout << a+i << b+j << endl;
//以上是合并出来的串
}
return 0;
}