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

การเขียนโปรแกรมเป็นศาสตร์ทางคอมพิวเตอร์ที่ผู้พัฒนาต้องใช้ความรู้และทักษะเพื่อแก้ปัญหาที่หลากหลาย หนึ่งในปัญหาเหล่านั้นคือการหา "Longest Common Subsequence (LCS)" หรือ ลำดับย่อยร่วมที่ยาวที่สุดในภาษาการเขียนโปรแกรม วันนี้เราจะสำรวจวิธีการหา LCS ในภาษา Java ด้วยการนำเสนอตัวอย่างโค้ด 3 ตัวอย่าง พร้อมอธิบายการทำงาน และให้ยกตัวอย่าง usecase ในโลกจริง

Longest Common Subsequence คืออะไร?

Longest Common Subsequence คือลำดับของตัวอักษรหรือสมาชิกส่วนประกอบที่ปรากฏในลำดับหลักทั้งหมดโดยที่ลำดับหรือการจัดเรียงตามลำดับเดียวกันไม่จำเป็นต้องต้องกัน ตัวอย่างเช่น LCS ของ "ABCDGH" และ "AEDFHR" คือ "ADH" ที่เพิ่มเติมก็คือ LCS ไม่จำเป็นต้องเป็นลำดับที่ต่อเนื่องกัน

ตัวอย่างโค้ดในภาษา Java

ต่อไปนี้คือตัวอย่างโค้ดที่ใช้คำนวณ LCS ในภาษา Java:

ตัวอย่างโค้ดที่ 1: การใช้ Recursive

 public class LCS {

    public static int lcsRecursive(String s1, String s2, int m, int n) {
        if (m == 0 || n == 0) {
            return 0;
        }
        if (s1.charAt(m - 1) == s2.charAt(n - 1)) {
            return 1 + lcsRecursive(s1, s2, m - 1, n - 1);
        } else {
            return Math.max(lcsRecursive(s1, s2, m, n - 1), lcsRecursive(s1, s2, m - 1, n));
        }
    }

    public static void main(String[] args) {
        String s1 = "ABCDGH";
        String s2 = "AEDFHR";
        int m = s1.length();
        int n = s2.length();

        System.out.println("Length of LCS: " + lcsRecursive(s1, s2, m, n));
    }
}

ปัญหาของการใช้ฟังก์ชันแบบ Recursive คือการมีประสิทธิภาพที่ต่ำเมื่อขนาดของสตริงและการเรียกฟังก์ชันซ้ำๆ มีจำนวนมาก

ตัวอย่างโค้ดที่ 2: การใช้ Dynamic Programming

 public class LCS {

    public static int lcsDynamic(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] L = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0) {
                    L[i][j] = 0;
                } else if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    L[i][j] = L[i - 1][j - 1] + 1;
                } else {
                    L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]);
                }
            }
        }
        return L[m][n];
    }

    public static void main(String[] args) {
        String s1 = "ABCDGH";
        String s2 = "AEDFHR";

        System.out.println("Length of LCS: " + lcsDynamic(s1, s2));
    }
}

การใช้วิธี Dynamic Programming จะช่วยเพิ่มประสิทธิภาพลดจำนวนการเรียกฟังก์ชันซ้ำๆ ลงและใช้เวลาในการคำนวณน้อยลงเมื่อเทียบกับการใช้ Recursive

ตัวอย่างโค้ดที่ 3: การพิมพ์ LCS

 public class LCS {

    public static void printLCS(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] L = new int[m + 1][n + 1];

        // Following steps build L[m+1][n+1] in bottom up fashion. Note
        // that L[i][j] contains length of LCS of s1[0..i-1] and s2[0..j-1]
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0) {
                    L[i][j] = 0;
                } else if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    L[i][j] = L[i - 1][j - 1] + 1;
                } else {
                    L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]);
                }
            }
        }

        // Following code is used to print LCS
        int index = L[m][n];
        int temp = index;
        char[] lcs = new char[index + 1];
        lcs[index] = '\u0000'; // Set the terminating character

        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                // Put current character in result
                lcs[index - 1] = s1.charAt(i - 1);

                // reduce values of i, j and index
                i--;
                j--;
                index--;
            }
            // If not same, then find the larger of two and
            // go in the direction of larger value
            else if (L[i - 1][j] > L[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        // Print the lcs
        System.out.print("LCS of " + s1+ " and "+ s2+ " is ");
        for (int k = 0; k <= temp; k++) {
            System.out.print(lcs[k]);
        }
    }

    public static void main(String[] args) {
        String s1 = "ABCDGH";
        String s2 = "AEDFHR";
        printLCS(s1, s2);
    }
}

การพิมพ์ LCS จำเป็นต้องมีการติดตามกลับไปยังตารางที่สร้างขึ้นโดยวิธี Dynamic Programming เพื่อหาลำดับที่ถูกต้อง

Usecase ในโลกจริง

LCS มีหลากหลาย usecase ในโลกจริง เช่น:

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

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