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