En Uzun Ortak Sonuç

İçindekiler

LCS'yi bulmak için Dinamik Programlamayı kullanma
En Uzun Yaygın Alt Sıra Algoritması
Python, Java ve C / C ++ Örnekleri
En Uzun Yaygın Müteakip Uygulamalar

Bu eğitimde, en uzun ortak alt dizinin nasıl bulunduğunu öğreneceksiniz. Ayrıca, C, C ++, Java ve Python'da en uzun ortak alt dizinin çalışma örneklerini bulacaksınız.

En uzun ortak alt dizi (LCS), alt dizinin öğelerinin orijinal diziler içinde ardışık konumları işgal etmeleri gerekmemesi koşuluyla, tüm verilen diziler için ortak olan en uzun alt dizi olarak tanımlanır.

S1 ve S2 verilen iki sekanssa, Z hem S1 hem de S2'nin bir altdizisi ise Z, S1 ve S2'nin ortak alt dizisidir. Ayrıca, Z , hem S1 hem de S2'nin indislerinin kesin olarak artan bir dizisi olmalıdır .

Kesin olarak artan bir dizide, orijinal dizilerden seçilen elemanların indisleri Z'de artan sırada olmalıdır.

Eğer

 S1 = (B, C, D, A, A, C, D)

Öyleyse, (A, D, B)öğelerin sırası aynı olmadığından (yani, tam olarak artan sıra olmadığından) S1'in bir alt dizisi olamaz.

LCS'yi bir örnekle anlayalım.

Eğer

 S1 = (B, C, D, A, A, C, D) S2 = (A, C, D, B, A, C)

Ardından, ortak alt diziler (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Bu alt diziler arasında (C, D, A, C)en uzun ortak alt dizidir. Dinamik programlamayı kullanarak bu en uzun ortak alt diziyi bulacağız.

Daha fazla ilerlemeden önce, dinamik programlama hakkında henüz bilgi sahibi değilseniz, lütfen dinamik programlamayı uygulayın.

LCS'yi bulmak için Dinamik Programlamayı kullanma

İki sekans alalım:

İlk sıra

İkinci Sıra

En uzun ortak alt diziyi bulmak için aşağıdaki adımlar izlenir.

n+1*m+1N ve m'nin sırasıyla X ve Y'nin uzunlukları olduğu bir boyut tablosu oluşturun . İlk satır ve ilk sütun sıfırlarla doldurulur. Bir tabloyu başlatın
Aşağıdaki mantığı kullanarak tablonun her bir hücresini doldurun.
Mevcut satır ve geçerli sütuna karşılık gelen karakter eşleşiyorsa, o zaman köşegen öğeye bir tane ekleyerek mevcut hücreyi doldurun. Çapraz hücreye bir ok doğrultun.
Aksi takdirde, geçerli hücreyi doldurmak için önceki sütundan ve önceki satır öğesinden maksimum değeri alın. Maksimum değeri olan hücreye bir ok getirin. Eşit iseler, herhangi birini işaret edin. Değerleri doldurun
Tablo dolana kadar 2. Adım tekrar edilir. Tüm değerleri doldurun
Son satırdaki ve son sütundaki değer, en uzun ortak alt dizinin uzunluğudur. Sağ alt köşe, LCS'nin uzunluğudur
En uzun ortak alt diziyi bulmak için, son öğeden başlayın ve okun yönünü takip edin. () Sembolüne karşılık gelen öğeler, en uzun ortak alt diziyi oluşturur. Oklara göre bir yol oluşturun

Bu nedenle, en uzun ortak alt dizi CD'dir.

LCS

Dinamik bir programlama algoritması, bir LCS problemini çözerken özyinelemeli algoritmadan nasıl daha etkilidir?

Dinamik programlama yöntemi, işlev çağrılarının sayısını azaltır. Her işlev çağrısının sonucunu depolar, böylece ilerideki çağrılarda fazlalık çağrılara gerek kalmadan kullanılabilir.

Yukarıdaki dinamik algoritmada, X'in öğeleri ile Y'nin öğeleri arasındaki her karşılaştırmadan elde edilen sonuçlar, gelecekteki hesaplamalarda kullanılabilmeleri için bir tabloda saklanır.

Dolayısıyla, dinamik bir yaklaşımla alınan zaman, tabloyu doldurmak için geçen süredir (yani O (mn)). Yineleme algoritması ise 2 ^{max (m, n)} karmaşıklığına sahiptir .

En Uzun Yaygın Alt Sıra Algoritması

 X ve Y iki verilen dizi olabilir. X boyutunda bir LCS tablosunu başlatın. Uzunluk * Y. uzunluk X. etiket = X Y. etiket = Y LCS (0) () = 0 LCS () (0) = 0 LCS'den başlayın ( 1) (1) X (i) ve Y (j) Karşılaştırın X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) LCS'yi işaret edin (i) (j) Başka LCS (i) (j) = maks (LCS (i-1) (j), LCS (i) (j-1)) Bir oku maksimumu işaret et (LCS (i-1) ( j), LCS (i) (j-1))

Python, Java ve C / C ++ Örnekleri

Python Java C C ++

 # The longest common subsequence in Python # Function to find lcs_algo def lcs_algo(S1, S2, m, n): L = ((0 for x in range(n+1)) for x in range(m+1)) # Building the mtrix in bottom-up way for i in range(m+1): for j in range(n+1): if i == 0 or j == 0: L(i)(j) = 0 elif S1(i-1) == S2(j-1): L(i)(j) = L(i-1)(j-1) + 1 else: L(i)(j) = max(L(i-1)(j), L(i)(j-1)) index = L(m)(n) lcs_algo = ("") * (index+1) lcs_algo(index) = "" i = m j = n while i> 0 and j> 0: if S1(i-1) == S2(j-1): lcs_algo(index-1) = S1(i-1) i -= 1 j -= 1 index -= 1 elif L(i-1)(j)> L(i)(j-1): i -= 1 else: j -= 1 # Printing the sub sequences print("S1 : " + S1 + "S2 : " + S2) print("LCS: " + "".join(lcs_algo)) S1 = "ACADB" S2 = "CBDA" m = len(S1) n = len(S2) lcs_algo(S1, S2, m, n)

 // The longest common subsequence in Java class LCS_ALGO ( static void lcs(String S1, String S2, int m, int n) ( int()() LCS_table = new int(m + 1)(n + 1); // Building the mtrix in bottom-up way for (int i = 0; i <= m; i++) ( for (int j = 0; j <= n; j++) ( if (i == 0 || j == 0) LCS_table(i)(j) = 0; else if (S1.charAt(i - 1) == S2.charAt(j - 1)) LCS_table(i)(j) = LCS_table(i - 1)(j - 1) + 1; else LCS_table(i)(j) = Math.max(LCS_table(i - 1)(j), LCS_table(i)(j - 1)); ) ) int index = LCS_table(m)(n); int temp = index; char() lcs = new char(index + 1); lcs(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1.charAt(i - 1) == S2.charAt(j - 1)) ( lcs(index - 1) = S1.charAt(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences System.out.print("S1 : " + S1 + "S2 : " + S2 + "LCS: "); for (int k = 0; k <= temp; k++) System.out.print(lcs(k)); System.out.println(""); ) public static void main(String() args) ( String S1 = "ACADB"; String S2 = "CBDA"; int m = S1.length(); int n = S2.length(); lcs(S1, S2, m, n); ) )

 // The longest common subsequence in C #include #include int i, j, m, n, LCS_table(20)(20); char S1(20) = "ACADB", S2(20) = "CBDA", b(20)(20); void lcsAlgo() ( m = strlen(S1); n = strlen(S2); // Filling 0's in the matrix for (i = 0; i <= m; i++) LCS_table(i)(0) = 0; for (i = 0; i <= n; i++) LCS_table(0)(i) = 0; // Building the mtrix in bottom-up way for (i = 1; i <= m; i++) for (j = 1; j = LCS_table(i)(j - 1)) ( LCS_table(i)(j) = LCS_table(i - 1)(j); ) else ( LCS_table(i)(j) = LCS_table(i)(j - 1); ) ) int index = LCS_table(m)(n); char lcsAlgo(index + 1); lcsAlgo(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1(i - 1) == S2(j - 1)) ( lcsAlgo(index - 1) = S1(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences printf("S1 : %s S2 : %s ", S1, S2); printf("LCS: %s", lcsAlgo); ) int main() ( lcsAlgo(); printf(""); )

 // The longest common subsequence in C++ #include using namespace std; void lcsAlgo(char *S1, char *S2, int m, int n) ( int LCS_table(m + 1)(n + 1); // Building the mtrix in bottom-up way for (int i = 0; i <= m; i++) ( for (int j = 0; j <= n; j++) ( if (i == 0 || j == 0) LCS_table(i)(j) = 0; else if (S1(i - 1) == S2(j - 1)) LCS_table(i)(j) = LCS_table(i - 1)(j - 1) + 1; else LCS_table(i)(j) = max(LCS_table(i - 1)(j), LCS_table(i)(j - 1)); ) ) int index = LCS_table(m)(n); char lcsAlgo(index + 1); lcsAlgo(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1(i - 1) == S2(j - 1)) ( lcsAlgo(index - 1) = S1(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences cout << "S1 : " << S1 << "S2 : " << S2 << "LCS: " << lcsAlgo << ""; ) int main() ( char S1() = "ACADB"; char S2() = "CBDA"; int m = strlen(S1); int n = strlen(S2); lcsAlgo(S1, S2, m, n); )