题目链接：http://poj.org/problem?id=2250
思路分析：最长公共子序列问题的变形，只是把字符变成了字符串，按照最长公共子序列的思路即可以求解。
代码如下：
#include <stdio.h>
#include <string.h> #define IsEqual(a, b) strcmp((a), (b)) == 0
enum { Left, Up, UpAndLeft };
int XLen, YLen;
const int MAX_N = + ;
char X[MAX_N][], Y[MAX_N][];
int dp[MAX_N][MAX_N], r[MAX_N][MAX_N]; void PrintWords(int i, int j)
{
if (i == || j == )
return; if (r[i][j] == UpAndLeft)
{
PrintWords(i - , j - ); if (i == XLen && j == YLen)
printf("%s",X[i]);
else
printf("%s ", X[i]);
}
else
if (r[i][j] == Up)
PrintWords(i - , j);
else
PrintWords(i, j - );
} void Lcs( int XLen, int YLen )
{
for (int i = ; i <= XLen; ++i)
dp[i][] = ;
for (int j = ; j <= YLen; ++j)
dp[][j] = ; for (int i = ; i <= XLen; ++i)
for (int j = ; j <= YLen; ++j)
{
if (IsEqual(X[i], Y[j]))
{
dp[i][j] = dp[i - ][j - ] + ;
r[i][j] = UpAndLeft;
}
else
if (dp[i - ][j] >= dp[i][j - ])
{
dp[i][j] = dp[i - ][j];
r[i][j] = Up;
}
else
{
dp[i][j] = dp[i][j - ];
r[i][j] = Left;
}
}
} int main()
{
XLen = YLen = ; while (scanf("%s", X[XLen]) != EOF)
{
memset(dp, , sizeof(dp));
memset(r, -, sizeof(r)); while ()
{
scanf("%s", X[++XLen]);
if (strcmp("#", X[XLen]) == )
{
XLen--;
break;
}
} while ()
{
scanf("%s", Y[YLen++]);
if (strcmp("#", Y[YLen - ]) == )
{
YLen -= ;
break;
}
} Lcs(XLen, YLen);
PrintWords(XLen, YLen);
printf("\n");
XLen = YLen = ;
} return ;
}