การใช้งาน Longest common subsequent ในภาษา C++ แบบง่ายๆ พร้อมตัวอย่าง

การใช้ Longest Common Subsequence (LCS) ในภาษา C++ แบบง่ายๆ พร้อมตัวอย่างโค้ด

Longest Common Subsequence (LCS) คืออะไร? นี่เป็นคำถามที่นิสิตคอมพิวเตอร์หลายคนตั้งขึ้นเมื่อเริ่มศึกษาเกี่ยวกับ algorithms ขั้นสูง เรามาเริ่มทำความเข้าใจกันก่อนว่า LCS คืออะไร แล้วจะประยุกต์ใช้งานอย่างไรในภาษา C++ แบบง่ายๆ

LCS คือการหาลำดับย่อยที่ยาวที่สุดที่ปรากฏในทั้งสอง strings ที่ถูกเปรียบเทียบ มันเป็นคำนวณที่มีประโยชน์มากในหลายสาขาวิชา รวมถึง bioinformatics, การเปรียบเทียบไฟล์เช่น git diff, หรือแม้กระทั่งในขั้นตอนของ data compression.

เราจะทำการแก้ปัญหา LCS ในภาษา C++ โดยใช้ Dynamic Programming (DP), เพราะ DP ช่วยให้การคำนวณแต่ละครั้งไม่ต้องทำซ้ำหลายๆครั้งอย่างไร้ประโยชน์ เราจะสร้างตาราง DP ที่จะเก็บผลลัพธ์ของ subproblems ที่เคยคำนวณไว้แล้ว ดังตัวอย่างโค้ดด้านล่างนี้:

 #include<iostream>
#include<vector>
#include<string>
using namespace std;

string LCS(string X, string Y) {
    int m = X.size(), n = Y.size();
    vector<vector<int>> dp(m+1, vector<int>(n+1));

    // สร้างตาราง DP
    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            if(X[i-1] == Y[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }

    // สร้าง LCS จากตาราง DP
    int index = dp[m][n];
    string lcs(index, '#');
    int i = m, j = n;

    while(i > 0 && j > 0){
        if(X[i-1] == Y[j-1]){
            lcs[--index] = X[i-1];
            i--; j--;
        }
        else if(dp[i-1][j] > dp[i][j-1]) i--;
        else j--;
    }
    return lcs;
}

int main() {
    string X = "ABCBDAB";
    string Y = "BDCABB";

    string lcs = LCS(X, Y);
    cout << "Longest Common Subsequence: " << lcs << endl;
    return 0;
}

ในตัวอย่างด้านบน, เราได้สร้างฟังก์ชัน `LCS` ที่รับพารามิเตอร์เป็นสอง strings X และ Y และคำนวณหา LCS ของทั้งคู่ โดยเราจะสร้างตาราง DP ที่มีขนาด `(m+1) x (n+1)` เมื่อ `m` และ `n` คือความยาวของ X และ Y ตามลำดับ จากนั้นเราจะตรวจทุกตัวอักษรใน X และ Y และคำนวณตาราง DP ทีละตำแหน่ง จนได้ LCS ในที่สุด

Usecase ในโลกจริงของ LCS:

การเรียนรู้และทำความเข้าใจ LCS ในภาษา C++ ถือเป็นสิ่งสำคัญในการศึกษาโลกของ algorithms และการเขียนโปรแกรม ถ้าคุณต้องการเรียนรู้เพิ่มเติมเกี่ยวกับการโปรแกรมและ algorithms นี้, ที่ EPT (Expert-Programming-Tutor) เรามีหลักสูตรที่ช่วยให้คุณเข้าใจและนำไปประยุกต์ใช้ LCS และ algorithms อื่นๆอีกมากมายในงานของคุณ ขอเชิญพบกับพวกเราแล้วจะพาคุณไปยังโลกที่ไร้ขอบเขตของการโปรแกรมมิ่ง!

หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง