Problem 10405 Longest Common Subsequence，最長共同子字串

建議大家可以上網去找「最長共同子字串」的演算法，此演算法是由「最長連續共同子字串」推演而來。「最長共同子字串」的方法就是依序比對字串，將最佳比對結果逐一往陣列右下方推，推到最後，答案就出來了。
C 語言程式碼如下：

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

By David.K

p10405題目連結
回ACM題庫目錄
回首頁