ماذا يعني LCS في الخوارزميات وهياكل البيانات؟ شرح مبسّط مع مثال

اختصار LCS في مجال الخوارزميات يعني Longest Common Subsequence، أي أطول سلسلة فرعية مشتركة بين نصّين أو أكثر. والمقصود بها: أطول تتابع من الرموز يظهر داخل السلسلتين بنفس الترتيب، لكن من دون اشتراط أن تكون الرموز متجاورة. هذه النقطة الأخيرة هي جوهر المفهوم، وهي أكثر ما يخلط فيه المبتدئون.

قبل أن نكمل، انتبه لالتباس شائع جدًا: هناك مصطلح آخر قريب جدًا في التسمية هو LCS = Longest Common Substring (أطول سلسلة جزئية متصلة). الاسمان متشابهان لكن المعنى مختلف تمامًا، والخلط بينهما يوقعك في إجابة خاطئة أثناء المقابلات أو حل التمارين. لنوضح الفرق فورًا.

Subsequence أم Substring؟ الفرق الجوهري

الفرق كله في كلمة واحدة: التجاور.

• Subsequence (سلسلة فرعية): تحافظ على الترتيب، لكن يُسمح بتخطّي رموز بينها. مثلًا ADH هي سلسلة فرعية من ABCDGH.
• Substring (سلسلة جزئية): يجب أن تكون رموزها متتالية ومتلاصقة بلا فجوات. مثلًا CDG سلسلة جزئية من ABCDGH، لكن ADH ليست كذلك.

العنصر	Longest Common Subsequence	Longest Common Substring
التجاور	غير مطلوب (يُسمح بالفجوات)	مطلوب (رموز متلاصقة)
الترتيب	محفوظ	محفوظ
الاستخدام الأشهر	مقارنة الملفات، الجينات، أدوات diff	كشف التشابه النصي، البحث عن أنماط
النتيجة على نفس المدخلات	غالبًا أطول	غالبًا أقصر

عندما يُذكر LCS في سياق الخوارزميات وهياكل البيانات بشكل مطلق، فالمقصود في الأغلب هو Subsequence، لأنه المسألة الكلاسيكية في البرمجة الديناميكية.

مثال عملي يوضّح الفكرة

لنأخذ سلسلتين:

• X = ABCDGH
• Y = AEDFHR

نبحث عن أطول سلسلة فرعية مشتركة. لو تتبّعنا الرموز المشتركة مع الحفاظ على الترتيب نجد: A ثم D ثم H. إذًا:

• LCS = "ADH" وطولها 3.

لاحظ أننا تخطّينا رموزًا كثيرة (مثل B وC وE)، وهذا مسموح لأننا نتعامل مع subsequence. لو طُلب منّا substring متصل بدلًا من ذلك، لكانت النتيجة رمزًا واحدًا فقط (A أو D أو H)، لأن أيًّا من هذه الرموز لا تجاور غيرها في السلسلتين.

كيف تُحسب LCS خطوة بخطوة

الحل الفعّال يعتمد على البرمجة الديناميكية (Dynamic Programming) عبر جدول ثنائي الأبعاد. الفكرة أننا نبني الحل من الحالات الأصغر إلى الأكبر بدل تجربة كل الاحتمالات (التي يكون عددها أُسّيًا).

1. أنشئ جدولًا dp بأبعاد (m+1) × (n+1)، حيث m وn طولا السلسلتين. الصف والعمود الأولان يُملآن بأصفار (الحالة الأساسية: مقارنة مع سلسلة فارغة تعطي طولًا صفريًا).
2. مرّ على كل زوج من الرموز X[i] وY[j].
3. إذا تطابق الرمزان، فإن dp[i][j] = dp[i-1][j-1] + 1 — أي نأخذ حل الزاوية القُطرية ونزيده واحدًا.
4. إذا اختلفا، فإن dp[i][j] = max(dp[i-1][j], dp[i][j-1]) — أي نحتفظ بأفضل حل من الاتجاهين.
5. القيمة في الخانة الأخيرة dp[m][n] هي طول أطول سلسلة فرعية مشتركة.
6. لاسترجاع السلسلة نفسها (وليس طولها فقط)، نتتبّع الجدول رجوعًا من الخانة الأخيرة نحو البداية حسب الاتجاه الذي جاءت منه كل قيمة.

الفكرة الذهنية البسيطة: كلما تطابق حرفان، «امشِ قطريًا وزِد العدّاد»؛ وإذا اختلفا، «خُذ الأكبر من الأعلى أو اليسار».

التعقيد الزمني واستهلاك الذاكرة

• الزمن: O(m × n) لأننا نملأ كل خانة في الجدول مرة واحدة.
• الذاكرة: O(m × n) في التنفيذ المباشر، لكن يمكن خفضها إلى O(min(m, n)) إذا احتجنا الطول فقط، لأننا لا نحتاج سوى الصف السابق أثناء الحساب.

هذا التحسين مهم عمليًا عند التعامل مع نصوص أو تسلسلات جينية ضخمة، حيث قد يستهلك الجدول الكامل ذاكرة هائلة.

أين تُستخدم LCS فعليًا

• أدوات مقارنة الملفات وdiff: أنظمة التحكم في الإصدارات مثل Git تعتمد على أفكار مشتقّة من LCS لإظهار الأسطر المضافة والمحذوفة بين نسختين.
• البيولوجيا الحاسوبية: مقارنة تسلسلات الحمض النووي (DNA) أو البروتينات لاكتشاف التشابه التطوري بين الكائنات.
• مدقّقات الانتحال والتشابه النصي: قياس مدى تقارب مستندين.
• الاقتراحات والتصحيح التلقائي: ضمن حسابات «المسافة» بين السلاسل.

أخطاء شائعة يقع فيها المبتدئون

• الخلط بين subsequence وsubstring كما شرحنا؛ اقرأ نص السؤال جيدًا قبل البدء.
• افتراض أن LCS واحدة فريدة: قد يكون هناك أكثر من سلسلة فرعية مشتركة بنفس الطول الأقصى، وكلها إجابات صحيحة.
• محاولة الحل بالقوة الغاشمة (brute force): تجربة كل السلاسل الفرعية تكلّفتها أُسّية O(2^n) وتتعطّل مع المدخلات الكبيرة؛ البرمجة الديناميكية هي الحل السليم.

الأسئلة الشائعة

هل LCS تعني دائمًا Longest Common Subsequence؟ في سياق الخوارزميات نعم غالبًا، لكن الاختصار نفسه قد يشير إلى Longest Common Substring. حدّد المقصود من السياق أو اسأل صراحةً في المقابلات.

ما تعقيد خوارزمية LCS؟ O(m × n) زمنًا باستخدام البرمجة الديناميكية، حيث m وn طولا السلسلتين.

هل يمكن إيجاد LCS لأكثر من سلسلتين؟ نعم، لكن المسألة تصبح أصعب بكثير؛ التعقيد ينمو أُسّيًا مع عدد السلاسل وتُعدّ من المسائل الصعبة حسابيًا.

ما الفرق بين LCS ومسافة التحرير (Edit Distance)؟ كلاهما يقيس التشابه بين نصّين، لكن مسافة التحرير تحسب أقل عدد من عمليات الإضافة والحذف والاستبدال لتحويل نص إلى آخر، بينما LCS تركّز على أطول جزء مشترك مع الحفاظ على الترتيب.