En Uzun Ortak Alt Dizi

Dinamik Programlama O(m · n) O(m · n)

Alt problem yanıtlarından 2 boyutlu bir tablo kurarak iki dizenin paylaştığı en uzun alt diziyi bulur.

ε	ε	G	A	C
ε	·	·	·	·
A	·	·	·	·
G	·	·	·	·
C	·	·	·	·
A	·	·	·	·
T	·	·	·	·

Dize ADize B

1/49

Satır 0, kolon 0: boş dizginin alt dizisi yoktur.

Değişmezdp[i][j], a'nın ilk i ve b'nin ilk j karakteri için cevaptır — zaten nihai, bir daha ziyaret edilmez.

hesaplanıyorokuduğudolu

lcs.c

int max(int a, int b) { return a > b ? a : b; }
 
int lcs(const char *a, const char *b) {
    int m = strlen(a), n = strlen(b);
    int dp[m + 1][n + 1];
 
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else if (a[i - 1] == b[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
}

En Uzun Ortak Alt Dizi nasıl çalışır?

dp[i][j] = A'nın ilk i ve B'nin ilk j karakterinin LCS uzunluğu. Eşleşen karakter köşegeni 1 uzatır; aksi hâlde iki dizeden birinden karakter düşürmenin iyisi devralınır.

Ne zaman kullanılır?

Diff araçları, DNA hizalama, intihal tespiti — her 'iki dizi ne kadar benzer' sorusu.