W tym samouczku dowiesz się, w jaki sposób znajduje się najdłuższy wspólny podciąg. Znajdziesz również działające przykłady najdłuższego wspólnego podciągu w językach C, C ++, Java i Python.
Najdłuższa wspólna podsekwencja (LCS) jest definiowana jako najdłuższa podsekcja, która jest wspólna dla wszystkich danych sekwencji, pod warunkiem, że elementy tej podsekcji nie muszą zajmować kolejnych pozycji w pierwotnych sekwencjach.
Jeśli S1 i S2 są dwiema podanymi sekwencjami, to Z jest wspólnym podsekwencją S1 i S2, jeśli Z jest podsekwencją obu S1 i S2. Ponadto Z musi być ściśle rosnącą sekwencją indeksów zarówno S1, jak i S2.
W ściśle rosnącej kolejności indeksy elementów wybranych z pierwotnych sekwencji muszą być w porządku rosnącym w Z.
Jeśli
S1 = (B, C, D, A, A, C, D)
Wtedy (A, D, B)nie może być podciągiem S1, ponieważ kolejność elementów nie jest taka sama (tj. Nie jest sekwencją ściśle rosnącą).
Rozumiemy LCS na przykładzie.
Jeśli
S1 = (B, C, D, A, A, C, D) S2 = (A, C, D, B, A, C)
Następnie są wspólne podciągi (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …
Wśród tych podciągów (C, D, A, C)jest najdłuższy wspólny podciąg. Znajdziemy ten najdłuższy wspólny podciąg przy użyciu programowania dynamicznego.
Jeśli nie wiesz jeszcze o programowaniu dynamicznym, zanim przejdziesz dalej, przejdź przez programowanie dynamiczne.
Korzystanie z programowania dynamicznego w celu znalezienia LCS
Weźmy dwie sekwencje:
Pierwsza sekwencja 
Druga sekwencja
Następujące kroki są wykonywane w celu znalezienia najdłuższego wspólnego podciągu.
- Utwórz tabelę wymiarów,
n+1*m+1gdzie n i m to długości odpowiednio X i Y. Pierwszy wiersz i pierwsza kolumna są wypełnione zerami.
Zainicjuj tabelę - Wypełnij każdą komórkę tabeli, używając następującej logiki.
- Jeśli znak odpowiadający bieżącemu wierszowi i bieżącej kolumnie jest zgodny, wypełnij bieżącą komórkę, dodając ją do elementu przekątnego. Skieruj strzałkę na przekątną komórkę.
- W przeciwnym razie weź maksymalną wartość z poprzedniej kolumny i elementu poprzedniego wiersza do wypełnienia bieżącej komórki. Skieruj strzałkę na komórkę z maksymalną wartością. Jeśli są równe, wskaż dowolną z nich.
Wypełnij wartości - Krok 2 powtarza się, aż stół zostanie wypełniony.
Wypełnij wszystkie wartości - Wartość w ostatnim wierszu i ostatniej kolumnie to długość najdłuższego wspólnego podciągu.
Prawy dolny róg to długość LCS - Aby znaleźć najdłuższy wspólny podciąg, zacznij od ostatniego elementu i postępuj zgodnie z kierunkiem strzałki. Elementy odpowiadające symbolowi () tworzą najdłuższy wspólny podciąg.
Utwórz ścieżkę zgodnie ze strzałkami
Zatem najdłuższym wspólnym podciągiem jest CD.
LCS
W jaki sposób algorytm programowania dynamicznego jest bardziej wydajny niż algorytm rekurencyjny podczas rozwiązywania problemu LCS?
Metoda programowania dynamicznego zmniejsza liczbę wywołań funkcji. Przechowuje wynik każdego wywołania funkcji, dzięki czemu może być używany w przyszłych wywołaniach bez potrzeby tworzenia dodatkowych wywołań.
W powyższym algorytmie dynamicznym wyniki uzyskane z każdego porównania między elementami X i elementami Y są przechowywane w tabeli, aby można je było wykorzystać w przyszłych obliczeniach.
Zatem czas potrzebny na podejście dynamiczne to czas potrzebny na wypełnienie tabeli (tj. O (mn)). Natomiast algorytm rekurencji ma złożoność 2 max (m, n) .
Algorytm najdłuższej wspólnej sekwencji
X i Y to dwie podane sekwencje Inicjalizuj tabelę LCS o wymiarze X.length * Y.length X.label = X Y.label = Y LCS (0) () = 0 LCS () (0) = 0 Zacznij od LCS ( 1) (1) Porównaj X (i) i Y (j) Jeśli X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Skieruj strzałkę na LCS (i) (j) W przeciwnym razie LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Skieruj strzałkę na max (LCS (i-1) ( j), LCS (i) (j-1))
Przykłady w Pythonie, Javie i C / C ++
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); )
Najdłuższe popularne aplikacje następcze
- w kompresji danych dotyczących ponownego sekwencjonowania genomu
- do uwierzytelniania użytkowników w ich telefonach komórkowych poprzez podpisy w powietrzu
