非常标准的最长公共子序列问题，用动态规划就能轻松解决。应该所有的教科书上都讲过这道题吧。动态规划的时候注意不要把序列规模设的太小就好，生成1000就肯定没问题。
附上我的代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 1000

int dp[N+1][N+1];

int main()
{
    int i,j;
    int n_x,n_y;
    char x[N],y[N];

    while(scanf("%s %s",x,y)!=EOF)
    {
        n_x = strlen(x);
        n_y = strlen(y);
        for(i=0;i<=n_x;i++)
            dp[i][0] = 0;
        for(j=0;j<=n_y;j++)
            dp[0][j] = 0;
        for(i=1;i<=n_x;i++)
            for(j=1;j<=n_y;j++)
            {
                if(x[i-1] == y[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                {
                    if(dp[i-1][j] > dp[i][j-1])
                        dp[i][j] = dp[i-1][j];
                    else
                        dp[i][j] = dp[i][j-1];
                }
            }

        printf("%d\n",dp[n_x][n_y]);
    }

    return 0;
}