赤裸的最长公共子序列
坑爹的题,回车也算字符,只要是字符就要算才行,绝不能用scanf读取字符串
我用了滚动数组
#include <stdio.h> #include <string.h> #define MAXN 1005 char str1[MAXN], str2[MAXN]; int f[2][MAXN]; int main() { int n, i, j; int len1, len2; int k1, k2; while( gets(str1)) { gets(str2); len1 = strlen(str1); len2 = strlen(str2); memset(f,0,sizeof(f)); for(i=1; i<=len1; ++i) for(j=1; j<=len2; ++j) { k1 = i &1; k2 = (i+1) & 1; if(str1[i-1] == str2[j-1]) f[k1][j] = f[k2][j-1] + 1; else { if(f[k1][j-1] > f[k2][j]) f[k1][j] = f[k1][j-1]; else f[k1][j] = f[k2][j]; } } printf("%d\n",f[len1 &1][len2]); } return 0; }