DP: ən uzun ümumi alt ardıcıllıq

İki ardıcıllığın ən uzun ümumi alt ardıcıllığı (LCS) hər ikisində eyni sırada olan ən uzun hərf ardıcıllığıdır. Bu, diff alətlərinin və DNT müqayisəsinin əsasıdır.

Alt ardıcıllıq və alt sətir

• Alt sətir ardıcıl hərflərdən ibarətdir: "BCB", "ABCBDAB"-in alt sətridir.
• Alt ardıcıllıq sırasını saxlayır, amma hərflər buraxıla bilər: "BCBA", "ABCBDAB"-in alt ardıcıllığıdır.

X = "ABCBDAB" və Y = "BDCABA" üçün LCS-in uzunluğu 4-dür (məsələn, "BCBA").

Vəziyyət və keçid

• Vəziyyət: dp[i][j] — X-in ilk i və Y-nin ilk j hərfinin LCS uzunluğu.
• Baza: dp[0][j] = dp[i][0] = 0.
• Uyğunluq (X[i-1] == Y[j-1]): dp[i][j] = dp[i-1][j-1] + 1.
• Uyğunsuzluq: dp[i][j] = max(dp[i-1][j], dp[i][j-1]), bir hərfi atırıq.
• Cavab: dp[n][m].

def lcs_table(x, y):
    n, m = len(x), len(y)
    # dp[i][j]: LCS length of x[:i] and y[:j]
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if x[i - 1] == y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1              # match: extend
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])   # drop one letter
    return dp