#include<stdio.h>
#include<string.h>
#define N 2000
int max(int a, int b)
{
if(a>b)
return a;
else
return b;
}
char a[N], b[N];
int ch[N][N] = {0};
int main ()
{
int i, j, m, n;
while (scanf("%s%s", a, b)!=EOF)
{
memset(ch, 0 ,sizeof(ch)); //取零；
m = strlen(a);
n = strlen(b);
for (i = 1; i<=m; i++)
{
for(j = 1; j<=n; j++)
{
if(a[i-1] == b[j-1])
ch[i][j] = ch[i-1][j-1] + 1; //原因见下表；
else
ch[i][j] = max(ch[i-1][j], ch[i][j-1]);
}
}
printf("%d\n", ch[m][n]);
}
return 0;
}
例
a = abcfbc
b = abfcab
| a\b | a0 = a | a1 =b | a2 = c | a3 = f | a4 = b | a5 =c | a6 | a7 | a8 |
| b0 = a | 1 | 1 | 1 | 1 | 1 | 1 |
空格的值的求法见代码 if(a[i-1] == b[j-1]) ch[i][j] = ch[i-1][j-1] + 1; else ch[i][j] = max(ch[i-1][j], ch[i][j-1]); |
||
| b1 = b | 1 | 2 | 2 | 2 | 2 | 2 | |||
| b2 = f | 1 | 2 | 2 | 3 | 3 | 3 | |||
| b3 = c | 1 | 2 | 3 | 3 | 3 | 4 | |||
| b4 = a | 1 | 2 | 3 | 3 | 3 | 4 | |||
| b5 = b | 1 | 2 | 3 | 3 | 4 | 4 | |||
| b6 | |||||||||
| b7 | |||||||||
| b8 | |||||||||
原文：http://www.cnblogs.com/yishilin/p/4241851.html