Longest Common Subsequence

Niech lcs(i, j) oznacza wynik dla sufiksów text1[i:] i text2[j:]. Przyjrzyj się ich pierwszym literom. Jeśli są takie same, połącz je w parę: najdłuższy wspólny podciąg, który nie zawiera tej pary, może zamienić swoją pierwszą parę na tę parę, nie stając się krótszy. Zatem wynik to 1 + lcs(i+1, j+1).

Jeśli litery się różnią, nie można użyć obu, ponieważ każda z nich mogłaby być dopasowana tylko do późniejszej litery w drugim ciągu, a pary by się krzyżowały. Można więc odrzucić jedną z nich: wynik to max(lcs(i+1, j), lcs(i, j+1)). Gdy którykolwiek sufiks jest pusty, nie ma nic wspólnego i wynikiem jest 0.

To rozwiązanie jest powolne, ponieważ przy każdym niedopasowaniu rozpoczynają się dwa wywołania. Jeśli ciągi nie mają żadnej wspólnej litery, każde wywołanie napotyka niedopasowanie, dopóki jeden z ciągów się nie skończy, a liczba wywołań rośnie jak liczba sposobów przeplatania obu ciągów. Dla dwóch ciągów po 20 liter daje to około 2.8 × 10^11 wywołań; duże testy zawierają po 1000 liter. Istnieje jednak tylko (n+1) × (m+1) różnych par (i, j), więc niemal każde wywołanie powtarza wcześniejsze.

Stan. Niech dp[i][j] oznacza najdłuższy wspólny podciąg pierwszych i liter text1 i pierwszych j liter text2. Praca z prefiksami pozwala oznaczać pusty ciąg indeksem 0.

Rekurencja. Porównaj ostatnie litery obu prefiksów: text1[i-1] i text2[j-1]. Jeśli są równe, połącz je w parę: dp[i][j] = dp[i-1][j-1] + 1. Jeśli nie, pomiń jedną z nich: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). To samo rozumowanie co w rekurencji, tylko zaczynamy od końca. Przypadek bazowy: wiersz 0 i kolumna 0 mają wartość 0, ponieważ pusty prefiks nie ma nic wspólnego z żadnym ciągiem. Kolejność: każda komórka odczytuje komórkę powyżej, po lewej i po przekątnej w górę i w lewo, więc wypełnianie wiersz po wierszu, od lewej do prawej, zawsze zapewnia, że te komórki są już gotowe. Odpowiedzią jest dp[n][m].

Dla pear i reap wiersz dla pea to [0, 0, 1, 2, 2]. Wartość komórki dla rea wynosi 2, ponieważ a pasuje do a, więc jest równa wartości komórki dla pe i re, czyli 1, powiększonej o jeden. Ostatnia komórka, dla pear i reap, porównuje r z p. Litery te są różne, więc wybierana jest większa wartość spośród dwóch sąsiednich komórek: 2.

Tablica ma (n+1) × (m+1) komórek, a obliczenie każdej wymaga stałej liczby operacji: około 10^6 kroków dla dwóch ciągów po 1000 liter. Wersja rekurencji z memoizacją wypełnia te same komórki, ale jej wywołania rekurencyjne mogą sięgać głębokości n + m, co powoduje przepełnienie domyślnego stosu wywołań w językach takich jak Python.

Wiersz i tabeli odczytuje tylko wiersz i-1 i wcześniejsze komórki w tym samym wierszu. Gdy wiersz jest gotowy, żaden wiersz powyżej niego nie jest już odczytywany. Dlatego używaj dwóch tablic: prev dla ukończonego wiersza i cur dla wiersza, który jest wypełniany, a po każdym wierszu zamieniaj je miejscami. Rekurencja i kolejność pozostają dokładnie takie same.

Wspólny podciąg dwóch ciągów nie zależy od tego, który z nich jest pierwszy, więc możesz zamienić je miejscami i prowadzić wiersze wzdłuż krótszego ciągu. Każdy wiersz zawiera wtedy min(n, m) + 1 liczb: 1001 zamiast miliona komórek dla największych danych wejściowych, przy tej samej liczbie 10^6 kroków obliczeń.

Pierwszy element każdego wiersza odpowiada pustemu prefiksowi krótszego ciągu, więc musi pozostać równy 0. Odpowiedź to ostatni element ostatniego ukończonego wiersza.