最长公共字序列.cpp

 
输出
一个整数。表示最长各个子序列的长度。
格式：printf("%d
");
 
输入例子
programming
contest


 
输出例子
2


 
提示
 
来源
*/
#include<iostream>
#include<stdio.h>


#include<stdlib.h>
#include<string.h>
using namespace std;
char a[201],b[201];
int sum[201][201];
int la,lb;
void slove()
{int i,j;
    for(i=1;i<=la;i++)
       for(j=1;j<=lb;j++)
         {
             if(a[i]==b[j])
                sum[i][j]=sum[i-1][j-1]+1;
            else if(sum[i-1][j]>=sum[i][j-1])
                sum[i][j]=sum[i-1][j];
            else
                sum[i][j]=sum[i][j-1];
         }
}


int main()
{int i,j;
    memset(a,'0',201);
    memset(b,'0',201);
    memset(sum,0,201*201);
    for(i=1;;i++){
       scanf("%c",&a[i]);
       if(a[i]=='
') break;}
       la=i-1;
    for(j=1;;j++){
        scanf("%c",&b[j]);
        if(b[j]=='
') break;}
        lb=j-1;
    slove();
    cout<<sum[la][lb]<<endl;
    return 0;
}</span>