2010年9月17日 星期五

ACM 10405 - Longest Common Subsequence

#include <stdio.h>
#include <string.h>
#include <memory.h>
#define LEN 1000

char seq1[LEN + 1], seq2[LEN + 1];

int lcs_length(int s1Len, int s2Len)
{
int i, j;
int table[s1Len + 1][s2Len + 1];
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;
else if(table[i - 1][j] > table[i][j - 1])
table[i][j] = table[i - 1][j];
else
table[i][j] = table[i][j - 1];
}
}
return table[s1Len][s2Len];
}

int main()
{

while (gets(seq1))
{
gets(seq2);
int s1Len = strlen(seq1), s2Len = strlen(seq2);
printf("%d\n", lcs_length(s1Len, s2Len));
}

return 0;
}


回目錄
回首頁

沒有留言 :

張貼留言

Related Posts Plugin for WordPress, Blogger...