PKU 1458的加強(qiáng)版本，思想類似，都是求最長公共子序列，而此題要求輸出最長子序列并且子序列是一個(gè)字符串不是一個(gè)單詞。DP的時(shí)候注意保存路徑就可以了。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 105
#define MAX(a, b) (a > b ? a : b)
char s1[N][35], s2[N][35], s[N + 2][35];
int a[N][N], p[N][N];
int dir[3][2] = {{-1, -1}, {0, -1}, {-1, 0}};
int main()
{
int l1 = 0, l2 = 0, top;
while(~scanf("%s", &s1[l1++]))
{
while(scanf("%s", &s1[l1]), strcmp(s1[l1++], "#"));
while(scanf("%s", &s2[l2]), strcmp(s2[l2++], "#"));
l1--, l2--;
//printf("l1 = %d, l2 = %d\n", l1, l2);
memset(a, 0, sizeof(a));
memset(p, -1, sizeof(p));
for(int i = 0; i < l1; i++)
{
for(int j = 0; j < l2; j++)
{
if(!strcmp(s1[i], s2[j]))
{
a[i + 1][j + 1] = a[i][j] + 1;
p[i + 1][j + 1] = 0;
}
else
{
a[i + 1][j + 1] = MAX(a[i][j], MAX(a[i + 1][j], a[i][j + 1]));
if(a[i + 1][j + 1] == a[i][j]) p[i + 1][j + 1] = 0;
else if(a[i + 1][j + 1] == a[i + 1][j]) p[i + 1][j + 1] = 1;
else p[i + 1][j + 1] = 2;
}
}
}
top = 0;
while(p[l1][l2] != -1)
{
if(!strcmp(s1[l1 - 1], s2[l2 - 1])) strcpy(s[top++], s1[l1 - 1]);
int t = p[l1][l2];
l1 += dir[t][0], l2 += dir[t][1];
}
for(int i = top - 1; i >= 0; i--)
{
if(i) printf("%s ", s[i]);
else printf("%s\n", s[i]);
}
// printf("%d\n", a[l1][l2]);
l1 = l2 = 0;
}
return 0;
}