2011-10-02 09:16:51Morris

a252. Another LCS

a252. Another LCS

內容 :

        一般LCS問題( Longest Common subsequence, 最長共同子字串)就是給定兩個字串,求出他們的LCS。為了理解這裡子字串定義,舉例來說,對於字串

abccdda

        abcaddaacabda等都是它的子字串,但adcbddebddd等不是他的子字串。

        對於兩個字串accbbeffgfcebg,他們的LCS長度為 3,而LCScbgceg

        現在我們把問題弄得難一點,給三個字串,請求出他們的LCS長度為多少?

輸入說明 :

        每個測資檔僅包含一筆測資,每筆測資有三個字串。測資保證三個字串的長度都不超過100,而且字串皆由小寫字母組成。

輸出說明 :

        對每筆測資,輸出LCS的長度。

範例輸入 :

abe
acb
babcd

範例輸出 :

2

提示 :

背景知識: DP

出處 :

成功高中校內賽初賽 第三題 (管理:david942j)



作法 : 同一般的 LCS, 做個延伸

/**********************************************************************************/
/*  Problem: a252 "Another LCS" from 成功高中校內賽初賽 第三題        */
/*  Language: C (577 Bytes)                                                       */
/*  Result: AC(2ms, 1.2MB) judge by this@ZeroJudge                                */
/*  Author: morris1028 at 2011-10-02 07:13:26                                     */
/**********************************************************************************/


#include<stdio.h>
#include<string.h>
int Max(int x, int y) {
    return x > y ? x : y;
}
int main() {
    char s1[101], s2[101], s3[101];
    char DP[101][101][101], i, j, k;
    while(scanf("%s %s %s", s1, s2, s3) == 3) {
        memset(DP, 0, sizeof(DP));
        for(i = 0; s1[i]; i++)
            for(j = 0; s2[j]; j++)
                for(k = 0; s3[k]; k++) {
                    if(s1[i] == s2[j] && s2[j] == s3[k])
                        DP[i+1][j+1][k+1] = DP[i][j][k] + 1;
                    else
                        DP[i+1][j+1][k+1] = Max(Max(DP[i+1][j+1][k], DP[i+1][j][k+1]), DP[i][j+1][k+1]);
                }
        printf("%d\n", DP[i][j][k]);
    }
    return 0;
}