طولانی‌ترین زیررشته مشترک (LCS)

طولانی‌ترین زیررشته/زیردنباله مشترک با DP: جدول دوبعدی، بازسازی جواب و کاربرد در diff و DNA

دو مسئله متفاوت!

مسئلهتعریفمثال (ABCBDGE، ACBDEF)
زیررشته (Substring)پیوسته«CBD»
زیردنباله (Subsequence)ترتیب حفظ، پیوستگی نه«ABCDE»

هر دو با DP حل می‌شوند — با رابطه‌های متفاوت.

زیردنباله مشترک (LCS) — کلاسیک‌ترین

رابطه بازگشتی:

اگر s[i] == t[j]:
    dp[i][j] = dp[i-1][j-1] + 1        # تطابق: اضافه کن
وگرنه:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # حذف یکی

جدول (m+1)×(n+1)؛ حالت پایه صفر. جواب = dp[m][n].

مثال جدول

s = "ACE", t = "ABCDE"

      ""  A  B  C  D  E
  ""   0  0  0  0  0  0
  A    0  1  1  1  1  1
  C    0  1  1  2  2  2
  E    0  1  1  2  2  3  ← LCS = 3 ("ACE")

بازسازی خود زیردنباله

از dp[m][n] به عقب: اگر s[i]==t[j] و dp[i][j]=dp[i-1][j-1]+1 ← کاراکتر مشترک؛ وگرنه به سمت بزرگ‌تر حرکت.

زیررشته مشترک (پیوسته)

تفاوت در رابطه: عدم تطابق = صفر (پیوستگی قطع شد!):

اگر s[i] == t[j]: dp[i][j] = dp[i-1][j-1] + 1
وگرنه: dp[i][j] = 0   ← پیوسته یا هست یا نیست!

جواب = بیشینه جدول (نه گوشه!).

کاربردهای واقعی

نکته: اگر فقط «طول» LCS را بخواهید و حافظه مهم باشد، دو سطر جدول کافی است — O(min(m,n)) حافظه! بازسازی جواب، جدول کامل می‌خواهد.

جمع‌بندی

این مبحث بخشی از دوره آموزش کامل الگوریتم‌ها است.

ابزارهای مرتبط