ZeroJudge A252: Another LCS

一般 LCS 問題 (Longest Common subsequence｜最長共同子字串) 就是給定兩個字串，求出他們的LCS。

為了理解這裡子字串定義，舉例來說，對於字串 abccdd：abc、adda、aca、bda 等都是它的子字串，但 adc、bdde、bddd 等不是他的子字串。

對於兩個字串 accbbeffg、fcebg，他們的LCS長度為 3，而 LCS 為 cbg 或 ceg。

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

範例測資

範例輸入範例輸出
每個測資檔僅包含一筆測資，每筆測資有三個字串。測資保證三個字串的長度都不超過 100，而且字串皆由小寫字母組成。對每筆測資，輸出 LCS 的長度。
abe
acb
babcd		2
ZeroJudge A252 範例測資

解題思路

假設三個字串分別為 a、b、c，宣告一個三維陣列，並且跑一個 a.length()*b.length()*c.length() 的 For 迴圈，如果 目前跑到的三個字元相等，則要判斷使否有任一數值是第一個，也就是 0，如果 i、j、k 有一個是 0 的話，則將 三維陣列[i][j][k] 設為 1，否則將 三維陣列[i][j][k] 設為 三維陣列[i-1][j-1][k-1]。

如果兩數不相等，則也要判斷 i、j、k 是否有 0，如果都不是的話就是將 三維陣列[i][j][k] 設為 三維陣列[i-1][j-1][k-1]。除此之外還要判斷只有 i、j、k 其中一個或兩個等於 0 的情況，這種情況就是將數值設為不是 0 的那邊 -1 位置。如果都是 0 的話就將 三維陣列[i][j][k] 設為 0。

最後的答案就是 三維陣列[a.length()-1][b.length()-1][c.length()-1]。

範例程式碼－ZeroJudge A252: Another LCS

#include <iostream>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    string a, b, c;
    cin >> a >> b >> c;
    int DP[100][100][100] = {};
    for (int i = 0; i<a.length(); i++) {
        for (int j = 0; j<b.length(); j++) {
            for (int k = 0; k<c.length(); k++) {
                if (a[i] == b[j] && b[j] == c[k]) {
                    if (i > 0 && j > 0 && k > 0) {
                        DP[i][j][k] = DP[i-1][j-1][k-1];
                    }
                    else {
                        DP[i][j][k] = 0;
                    }
                    DP[i][j][k]++;
                }
                else {
                    if (i > 0 && j > 0 && k > 0) {
                        DP[i][j][k] = max(max(DP[i-1][j][k], DP[i][j-1][k]), DP[i][j][k-1]);
                    }
                    else if (i > 0 && j > 0) {
                        DP[i][j][k] = max(DP[i-1][j][k], DP[i][j-1][k]);
                    }
                    else if (j > 0 && k > 0) {
                        DP[i][j][k] = max(DP[i][j-1][k], DP[i][j][k-1]);
                    }
                    else if (i > 0 && k > 0) {
                        DP[i][j][k] = max(DP[i-1][j][k], DP[i][j][k-1]);
                    }
                    else if (i > 0) {
                        DP[i][j][k] = DP[i-1][j][k];
                    }
                    else if (j > 0) {
                        DP[i][j][k] = DP[i][j-1][k];
                    }
                    else if (k > 0) {
                        DP[i][j][k] = DP[i][j][k-1];
                    }
                    else DP[i][j][k] = 0;
                }
            }
        }
    }
    cout << DP[a.length()-1][b.length()-1][c.length()-1] << "\n";
}

//ZeroJudge A252
//Dr. SeanXD
標籤

相關文章

發佈留言