求最长公共子序列LCS，用动态规划求解。
UVa的字符串可能含有空格，开始用scanf("%s", s);就WA了一次...那就用gets吧，怪不得要一行放一个字符串呢。
（本来想用fgets的，可是又放弃了，形式麻烦、代码长是一小方面，另一方面fgets把'\n'字符也读入，还要做额外的处理...虽然gets有传说中的缓冲区溢出漏洞，不过多加注意一下就好啦，个人认为代码还没大到要用那些工程性的东西的时候）
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 1000+10
using namespace std; char s1[MAXN], s2[MAXN];
int c[MAXN][MAXN]; int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
while (gets(s1) && gets(s2))
{
int m = strlen(s1);
int n = strlen(s2);
memset(c, , sizeof(c));
for (int i = ; i <= m; i++)
for (int j = ; j <= n; j++)
{
if (s1[i-] == s2[j-]) c[i][j] = c[i-][j-] + ;
else c[i][j] = max(c[i][j-], c[i-][j]);
}
printf("%d\n", c[m][n]);
}
return ;
}
在POJ中字符串用空格分割，字符串中不含空格，并且两个字符串在同一行上，用scanf("%s", s)替换get(s)就可以了
下面是打印LCS的代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 1000+10
using namespace std; char s1[MAXN], s2[MAXN];
int c[MAXN][MAXN]; void print_LCS(int i, int j)
{
if (i == || j == ) return;
if (s1[i-] == s2[j-])
{
print_LCS(i-, j-);
printf("%c", s1[i-]);
}
else if (c[i-][j] == c[i][j]) print_LCS(i-, j);
else if (c[i][j-] == c[i][j]) print_LCS(i, j-);
} int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
while (scanf("%s%s", s1, s2) != EOF)
{
int m = strlen(s1);
int n = strlen(s2);
memset(c, , sizeof(c));
for (int i = ; i <= m; i++)
for (int j = ; j <= n; j++)
{
if (s1[i-] == s2[j-]) c[i][j] = c[i-][j-] + ;
else c[i][j] = max(c[i][j-], c[i-][j]);
}
printf("%d\n", c[m][n]);
// print the LCS
print_LCS(m, n);
printf("\n");
}
return ;
}
2