Tìm Chuỗi Con Chung Dài Nhất (LCS) trong C# và Quy Hoạch Động

Thuật toán Tìm Chuỗi Con Chung Dài Nhất (Longest Common Subsequence - LCS) trong C#

Bài toán tìm chuỗi con chung dài nhất (LCS) giữa hai chuỗi là một trong những bài toán quan trọng trong lý thuyết về chuỗi và quy hoạch động. Mục tiêu của bài toán là tìm chuỗi con dài nhất mà cả hai chuỗi đều chứa dưới dạng chuỗi con.

Phương pháp Quy hoạch Động

Để giải bài toán LCS bằng quy hoạch động, chúng ta sử dụng một bảng 2D để lưu trữ độ dài của LCS của các đoạn con của hai chuỗi. Giả sử dp[i][j] là độ dài của LCS của hai đoạn con s1[0...i-1] và s2[0...j-1]. Ta có các trường hợp sau:

• Nếu s1[i-1] == s2[j-1], thì dp[i][j] = dp[i-1][j-1] + 1.
• Nếu s1[i-1] != s2[j-1], thì dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Mã C# cho Thuật toán LCS

Dưới đây là mã C# để tìm chuỗi con chung dài nhất giữa hai chuỗi:

using System;

class LongestCommonSubsequence
{
    // Hàm tìm LCS giữa hai chuỗi
    public static int FindLCS(string s1, string s2)
    {
        int m = s1.Length;
        int n = s2.Length;
        int[,] dp = new int[m + 1, n + 1];

        // Lặp qua từng ký tự của s1 và s2
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                // Nếu ký tự hiện tại của s1 và s2 giống nhau
                if (s1[i - 1] == s2[j - 1])
                {
                    dp[i, j] = dp[i - 1, j - 1] + 1;
                }
                else
                {
                    dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
                }
            }
        }

        return dp[m, n];
    }

    // Hàm chính để chạy chương trình
    public static void Main()
    {
        string s1 = "AGGTAB";
        string s2 = "GXTXAYB";

        int lcsLength = FindLCS(s1, s2);
        Console.WriteLine("Độ dài chuỗi con chung dài nhất là: " + lcsLength);
    }
}

Giải thích mã

1. Khởi tạo bảng dp:

   • dp[i, j] lưu trữ độ dài của LCS của đoạn con s1[0...i-1] và s2[0...j-1].

2. Lặp qua từng ký tự của hai chuỗi:

   • Nếu ký tự của s1 và s2 tại vị trí hiện tại giống nhau (s1[i-1] == s2[j-1]), thì dp[i, j] = dp[i-1, j-1] + 1.
   • Nếu không, dp[i, j] là giá trị lớn hơn giữa dp[i-1, j] và dp[i, j-1].

3. Kết quả:

   • Giá trị tại dp[m, n] là độ dài của chuỗi con chung dài nhất giữa s1 và s2.

Ví dụ

Nếu bạn chạy đoạn mã trên với hai chuỗi s1 = "AGGTAB" và s2 = "GXTXAYB", kết quả sẽ là:

Độ dài chuỗi con chung dài nhất là: 4

Chuỗi con chung dài nhất ở đây là "GTAB".

Kết luận

Bài toán LCS là một bài toán kinh điển trong lý thuyết chuỗi và quy hoạch động. Thuật toán trên giúp bạn tìm được độ dài chuỗi con chung dài nhất giữa hai chuỗi bất kỳ với độ phức tạp thời gian là O(m * n), trong đó m và n là độ dài của hai chuỗi.