2013年7月17日 星期三

最長共同子序列

#include <iostream>
#include <string>
using namespace std;
#define LEN 1000
int table[LEN + 1][LEN + 1];
char seq1[LEN + 1], seq2[LEN + 1];
string cs="";
int lcs_length(int s1Len, int s2Len)
{
    int i, j;  
    memset(table, 0, sizeof(table));

    for(i = 1; i <= s1Len; ++i) {
        for(j = 1; j <= s2Len; ++j) {
            if(seq1[i - 1] == seq2[j - 1])
            {   
     table[i][j] = table[i - 1][j - 1] + 1;
     cs=cs + seq1[i - 1];
   }
            else
     table[i][j] = max(table[i - 1][j],table[i][j - 1]);
        }
   }
   return table[s1Len][s2Len];
}
int main()
{
   
    while (cin >>seq1 >> seq2)
    {
        int s1Len = strlen(seq1), s2Len = strlen(seq2);
  cout << lcs_length(s1Len, s2Len) << "--" << cs << endl;
    }
   
    return 0;
}