#include <stdio.h>
#include <stdlib.h>

//求最長公共子序列
//兩種做法：遞歸、狀態數組表

/*
測試數據如下
輸入: 
7 5
1 3 4 4 7 8 9
3 4 4 8 10
輸出: 
4
*/
int cal(int *a,int *b,int ca,int cb)
{
	int tempa,tempb;
	if(ca==-1||cb==-1) return 0;
	else if(a[ca]==b[cb]) return cal(a,b,ca-1,cb-1)+1;
	else 
	{
		tempa=cal(a,b,ca-1,cb);
		tempb=cal(a,b,ca,cb-1);
		if(tempa<tempb) return tempb;
		else return tempa;
	}
}

int main()
{
	int counta,countb,a[10],b[10],i;
	scanf("%d %d",&counta,&countb);
	for(i=0;i<counta;i++) scanf("%d",&a[i]);
	for(i=0;i<countb;i++) scanf("%d",&b[i]);
	printf("%d\n",cal(a,b,counta-1,countb-1));
	return 0;
}

===========================================

#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <string.h>
using namespace std;

//求最長公共子序列 NOJ 1022
#define NMAX 1005
int f[NMAX][NMAX];//使用數組存放狀態，以空間換時間
char s1[NMAX];
char s2[NMAX];

void cal(char *s1,char *s2,int len1,int len2)
{
    int i,j;
	memset(f,0,sizeof(f));
    for(i=1;i<=len1;i++)
    {
        for(j=1;j<=len2;j++)
        {	//該位置字符相同，上一狀態加1即可得
            if(s1[i-1]==s2[j-1]) f[i][j]=f[i-1][j-1]+1;
            else
            {	//若字符不相同，則為上一狀態的最大值
                if(f[i][j-1]<f[i-1][j]) f[i][j]=f[i-1][j];
                else f[i][j]=f[i][j-1];
            }
        }
    }
}


int main()
{
    int i,j;
    while(scanf("%s%s",&s1,&s2)!=EOF)
    {
        i=strlen(s1);
        j=strlen(s2);
        cal(s1,s2,i,j);
        printf("%d\n",f[i][j]);
    }
    return 0;
}