ما هي Longest Common Substring؟ إيجاد أطول جزء متصل مشترك باستخدام Dynamic Programming

تهدف مسألة Longest Common Substring إلى إيجاد أطول جزء متصل يظهر داخل سلسلتين.

مثال:

ABABC
BABCA

أطول جزء مشترك متصل هو:

BABC

وبالتالي:

Length = 4

الكلمة المهمة هنا هي متصل. يجب أن تظهر جميع الأحرف بجانب بعضها من دون انقطاع.

ما هو Substring؟

في السلسلة:

ABCDE

تعد هذه أمثلة صحيحة:

ABC
BCD
DE

أما:

ACE

فليست Substring لأن الأحرف ليست متجاورة.

Dynamic Programming

نعرّف:

dp[i][j]

على أنه طول أطول Substring مشترك ينتهي تحديداً عند a[i - 1] وb[j - 1].

إذا كان الحرفان متساويين:

dp[i][j] = dp[i - 1][j - 1] + 1

أما عند الاختلاف:

dp[i][j] = 0

سبب الصفر هو أن Substring يجب أن يبقى متصلاً، وأي mismatch يقطع السلسلة الحالية.

مثال

للسلسلتين:

a = ABABC
b = BABCA

يمكن أن يكون جدول DP:

      B  A  B  C  A
A     0  1  0  0  1
B     1  0  2  0  0
A     0  2  0  0  1
B     1  0  3  0  0
C     0  0  0  4  0

أكبر قيمة هي 4 وتمثل BABC.

TypeScript

function longestCommonSubstring(
  a: string,
  b: string
): string {
  const dp = Array.from(
    { length: a.length + 1 },
    () => new Array(b.length + 1).fill(0)
  );

  let maxLength = 0;
  let endIndex = 0;

  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;

        if (dp[i][j] > maxLength) {
          maxLength = dp[i][j];
          endIndex = i;
        }
      }
    }
  }

  return a.slice(endIndex - maxLength, endIndex);
}

التعقيد

إذا كان طول السلسلتين n وm:

Time Complexity: O(n × m)
Space Complexity: O(n × m)

ويمكن تقليل الذاكرة إلى:

O(min(n, m))

باستخدام صفين فقط من جدول DP.

الفرق عن Longest Common Subsequence

في Substring يجب أن تكون الأحرف متجاورة.

أما Subsequence فيسمح بتجاوز بعض الأحرف مع الحفاظ على الترتيب.

مثلاً:

ABCDEF
ACEF

يمكن أن تكون ACEF عبارة عن Common Subsequence، لكنها ليست Substring في ABCDEF.

أهم فرق في DP هو أنه عند mismatch في Longest Common Substring نكتب:

dp[i][j] = 0

أما في LCS فعادة نأخذ أفضل نتيجة من الحالات المجاورة.

تطبيقات عملية

يمكن استخدام الفكرة في:

• String Similarity
• Data Cleaning
• CRM Deduplication
• DNA Sequence Analysis
• مقارنة الإصدارات
• اكتشاف الأجزاء المتكررة في المستندات
• Log Analysis

في CRM مثلاً قد تساعد Substring طويلة مشتركة بين اسمين في اكتشاف سجلين متشابهين، لكن يجب دمجها مع Email وPhone ومقاييس أخرى.

عدة إجابات متساوية

قد توجد أكثر من Substring لها نفس الطول الأقصى.

مثلاً:

abcXYZ123
abcABC123

كل من:

abc
123

له طول 3.

سؤال مقابلات

السؤال الشائع هو إيجاد طول أو قيمة أطول Substring مشتركة بين سلسلتين.

يجب الانتباه إلى:

• الاتصال Contiguity
• تعريف حالة DP
• إعادة القيمة إلى صفر عند mismatch
• تخزين Max Length
• التعقيد O(n × m)

الخلاصة

Longest Common Substring تجد أطول جزء متصل مشترك بين سلسلتين.

العلاقة الأساسية:

Match    → dp[i - 1][j - 1] + 1
Mismatch → 0

والحل التقليدي باستخدام Dynamic Programming يعمل في زمن O(n × m).