فهم العنصر المشترك الأطول (Longest Common Subsequence – LCS) مع أمثلة في Python، Java، و C

1. مقدمة عن المشكلة

وصف المشكلة:
العنصر المشترك الأطول (Longest Common Subsequence – LCS) هو مشكلة العثور على أطول سلسلة يمكن أن تكون موجودة بالتسلسل في سلسلتين أو أكثر. على عكس البحث عن العنصر المشترك الأطول المتجاور، فإن عناصر السلسلة في LCS لا تحتاج إلى أن تكون متجاورة ولكن يجب أن تحتفظ بنفس الترتيب النسبي.

حالة استخدام:
تستخدم LCS بشكل شائع في مقارنة السلاسل النصية، مثل مقارنة الملفات النصية للعثور على التغييرات أو في التطبيقات البيولوجية مثل مقارنة التسلسل الجيني للعثور على التشابه بين الجينات.

المدخلات والمخرجات:

• المدخلات: سلسلتان نصيتان.
• المخرجات: طول العنصر المشترك الأطول.

2. شرح تعليمي للحل

مفهوم العنصر المشترك الأطول:

نستخدم تقنية البرمجة الديناميكية لحل مشكلة LCS. الفكرة الأساسية هي بناء جدول ثنائي الأبعاد (2D table) حيث يشير كل خلية فيه إلى طول LCS حتى ذلك الموضع.

1. إذا كانت الأحرف في نهاية كل سلسلة متطابقة، فسيكون طول LCS هو طول LCS من السلسلتين مع استبعاد هذا الحرف +1.
2. إذا لم تتطابق الأحرف، فإننا نأخذ الحد الأقصى من LCS الممكن بين استبعاد الحرف الأخير من إما السلسلة الأولى أو السلسلة الثانية.

تعقيد الوقت:

• O(m * n)، حيث m و n هما أطوال السلسلتين.

تعقيد المساحة:

• O(m * n) لتخزين جدول البرمجة الديناميكية.

3. الحل في Python

def lcs(X, Y):
    m = len(X)
    n = len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # بناء جدول البرمجة الديناميكية
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            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])

    return dp[m][n]

# استخدام المثال
X = "AGGTAB"
Y = "GXTXAYB"
print("طول العنصر المشترك الأطول هو:", lcs(X, Y))

4. الحل في Java

public class LCS {

    // دالة لإيجاد طول LCS
    int lcs(char[] X, char[] Y, int m, int n) {
        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 (X[i - 1] == Y[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) {
        LCS lcs = new LCS();
        String s1 = "AGGTAB";
        String s2 = "GXTXAYB";
        char[] X = s1.toCharArray();
        char[] Y = s2.toCharArray();
        int m = X.length;
        int n = Y.length;
        System.out.println("طول العنصر المشترك الأطول هو: " + lcs.lcs(X, Y, m, n));
    }
}

5. الحل في C

#include <stdio.h>
#include <string.h>

// دالة لإيجاد طول LCS
int lcs(char *X, char *Y, int m, int n) {
    int L[m + 1][n + 1];
    int i, j;

    // بناء جدول البرمجة الديناميكية
    for (i = 0; i <= m; i++) {
        for (j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                L[i][j] = 0;
            else if (X[i - 1] == Y[j - 1])
                L[i][j] = L[i - 1][j - 1] + 1;
            else
                L[i][j] = (L[i - 1][j] > L[i][j - 1]) ? L[i - 1][j] : L[i][j - 1];
        }
    }
    return L[m][n];
}

// دالة القيادة لاختبار ما سبق
int main() {
    char X[] = "AGGTAB";
    char Y[] = "GXTXAYB";
    int m = strlen(X);
    int n = strlen(Y);
    printf("طول العنصر المشترك الأطول هو: %d\n", lcs(X, Y, m, n));
    return 0;
}