noj最长公共子序列

1041.最长公共子序列

时限：1000ms 内存限制：200000K  总时限：3000ms

描述

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=<x1, x2,…, xm>，则另一序列Z=<z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列 <i1, i2,…, ik>，使得对于所有j=1,2,…,k有：

Xij ＝ Zj

如果一个序列S即是A的子序列又是B的子序列，则称S是A、B的公共子序列。
求A、B所有公共子序列中最长的序列的长度。

 

输入

输入共两行，每行一个由字母和数字组成的字符串，代表序列A、B。A、B的长度不超过200个字符。

 

输出

一个整数，表示最长各个子序列的长度。
格式：printf("%d ");

 

输入样例

programming
contest

 

输出样例

2

#include <stdio.h>
#include <string.h>

char a[201],b[201];
int lena,lenb;
int c[202][202];

void LCS()
{
     int i=0,j=0;
     for(i=0;i<lena;i++)
          for(j=0;j<lenb;j++)
     {
          if(a[i]==b[j])
          {
               c[i+1][j+1] = c[i][j]+1;
          }
          else if(c[i+1][j]>=c[i][j+1])
               c[i+1][j+1] = c[i+1][j];
          else
               c[i+1][j+1] = c[i][j+1];
     }
     printf("%d
",c[lena][lenb]);
}

int main()
{
     scanf("%s",a);
     scanf("%s",b);
     lena = strlen(a);
     lenb = strlen(b);
     memset(c,0,sizeof(c));
     LCS();
     return 0;
}