1
2 #include
3 #include
4
5 int lcsCount[1001][1001];
6 char a[1001],b[1001];
7
8 int max(const int x, const int y){
9 return x>y?x:y;
10 }
11
12 void lcs(){
13 memset(lcsCount, 0, sizeof(lcsCount));
14 int x = strlen(a);
15 int y = strlen(b);
16 for(int i = 0; i <= x; i++){
17 for(int j = 0; j <= y; j++){
18 if(i==0 || j ==0)
19 lcsCount[i][j] = 0;
20 else if(a[i-1] == b[j-1])
21 lcsCount[i][j] = lcsCount[i-1][j-1]+1;
22 else{
23 lcsCount[i][j] = max(lcsCount[i][j-1], lcsCount[i-1][j]);
24 }
25 }
26 }
27 }
28
29 int main()
30 {
31 while(scanf("%s %s", a, b)!=EOF){
32 lcs();
33 printf("%d\n", lcsCount[strlen(a)][strlen(b)]);
34 }
35
36 return 0;
37 }