תת־סדרה משותפת ארוכה ביותר

מוצא את התת־סדרה הארוכה ביותר המשותפת לשתי סדרות.

סדרה 1

ABCDE

סדרה 2

ACE

שלב 1 מתוך 18

מצא את התת־סדרה המשותפת הארוכה ביותר של "ABCDE" ו־"ACE". בנה טבלה בגודל (6)×(4) מלמטה למעלה.

▶אלגוריתם

LCS(s1, s2):
dp[0][j] = dp[i][0] = 0 for all i, j
for i = 1..n, j = 1..m:
if s1[i−1] == s2[j−1]:
  dp[i][j] = dp[i−1][j−1] + 1
else:
  dp[i][j] = max(dp[i−1][j], dp[i][j−1])
backtrack to reconstruct LCS string

מקרא

התא הנוכחי

תלויות

מסלול אופטימלי

מחושב

dp[i][j] = אורך ה־LCS של i התווים הראשונים של "ABCDE" ו־j התווים הראשונים של "ACE".

1 / 18מהירות