杭電 hdu 1159

Common Subsequence：

#include<iostream>
#include<cstring>
using namespace std;
#define M 1000
#define N 1000
int c[M][N];
int lcs_len(char *a,char *b)
{
    int m=strlen(a),n=strlen(b),i,j;
    for(i=0;i<=m;++i)
        for(j=0;j<=n;++j)
            c[i][j]=0;
    for(i=0;i<=m;i++)
        c[i][0]=0;
      for(j=0;j<=n;j++)
          c[0][j]=0;
      for(i=1;i<=m;i++){
        for(j=1;j<=n;j++){
              if(a[i-1]==b[j-1])
                c[i][j]=c[i-1][j-1]+1;
              else
                if(c[i-1][j]>c[i][j-1])
                    c[i][j]=c[i-1][j];
            else
                c[i][j]=c[i][j-1];
         }
    }
    int maxnum=-32768;
    for(i=0;i<=m;++i)
        for(j=0;j<=n;++j)
            if(c[i][j]>maxnum)
                maxnum=c[i][j];
    return maxnum;
}
int main(){
    char a[M],b[M];
    while(cin>>a>>b)
        cout<<lcs_len(a,b)<<endl;
    return 0;
}

本文出自 “菜鳥的進階之路” 博客，請務必保留此出處http://beyond316.blog.51cto.com/7367775/1272550