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;
}

回目錄
回首頁