Найдовша загальна послідовність

У цьому підручнику ви дізнаєтесь, як знайдено найдовшу загальну підпослідовність. Також ви знайдете робочі приклади найдовшої загальної підпослідовності в C, C ++, Java та Python.

Найдовша загальна підпослідовність (LCS) визначається як найдовша підпослідовність, спільна для всіх заданих послідовностей, за умови, що елементи підпослідовності не повинні займати послідовні позиції в оригінальних послідовностях.

Якщо S1 і S2 - це дві задані послідовності, тоді Z є загальною підпослідовністю S1 і S2, якщо Z є підпослідовністю як S1, так і S2. Крім того, Z повинна бути суворо зростаючою послідовністю індексів як S1, так і S2.

У строго зростаючій послідовності індекси елементів, вибраних з вихідних послідовностей, повинні бути у порядку зростання у Z.

Якщо

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

Тоді, (A, D, B)не може бути підпослідовністю S1, оскільки порядок елементів не однаковий (тобто. Не суворо зростаюча послідовність).

Давайте розберемося з LCS на прикладі.

Якщо

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

Тоді загальними підпослідовностями є (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Серед цих підпослідовностей (C, D, A, C)є найдовша загальна підпослідовність. Ми збираємось знайти цю найдовшу загальну підпослідовність за допомогою динамічного програмування.

Перш ніж продовжувати далі, якщо ви ще не знаєте про динамічне програмування, пройдіть динамічне програмування.

Використання динамічного програмування для пошуку LCS

Візьмемо дві послідовності:

Перша послідовність

Друга послідовність

Для пошуку найдовшої загальної підпослідовності виконуються наступні кроки.

Створіть таблицю розмірностей, n+1*m+1де n і m - довжини X та Y відповідно. Перший рядок і перший стовпець заповнені нулями. Ініціюйте таблицю
Заповніть кожну комірку таблиці, використовуючи таку логіку.
Якщо символ, що відповідає поточному рядку та поточному стовпцю, збігається, заповніть поточну комірку, додавши одну до діагонального елемента. Наведіть стрілку на діагональну комірку.
В іншому випадку приймають максимальне значення з попереднього стовпця та попереднього елемента рядка для заповнення поточної комірки. Наведіть стрілку на клітинку з максимальним значенням. Якщо вони рівні, вкажіть на будь-який з них. Заповніть значення
Крок 2 повторюється, поки таблиця не заповниться. Заповніть усі значення
Значення в останньому рядку та останньому стовпці - це довжина найдовшої загальної підпослідовності. Нижній правий кут - це довжина LCS
Для того, щоб знайти найдовшу загальну підпослідовність, почніть з останнього елемента і дотримуйтесь напряму стрілки. Елементи, що відповідають символу (), утворюють найдовшу загальну підпослідовність. Створіть контур відповідно до стрілок

Таким чином, найдовшою загальною підпослідовністю є CD.

LCS

Наскільки алгоритм динамічного програмування ефективніший за рекурсивний алгоритм при вирішенні задачі LCS?

Метод динамічного програмування зменшує кількість викликів функцій. Він зберігає результат кожного виклику функції, щоб його можна було використовувати в майбутніх дзвінках без необхідності зайвих викликів.

У наведеному вище динамічному алгоритмі результати, отримані в результаті кожного порівняння між елементами X та елементами Y, зберігаються в таблиці, щоб їх можна було використовувати в майбутніх обчисленнях.

Отже, час, зайнятий динамічним підходом, - це час, необхідний для заповнення таблиці (тобто O (mn)). Тоді як алгоритм рекурсії має складність 2 ^{max (m, n)} .

Найдовший загальний алгоритм наступних послідовностей

 X і Y - дві задані послідовності Ініціалізація таблиці LCS розмірності X. довжина * Y. довжина X. мітка = X Y. мітка = Y LCS (0) () = 0 LCS () (0) = 0 Почніть з LCS ( 1) (1) Порівняйте X (i) та Y (j) Якщо X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Наведіть стрілку на LCS (i) (j) Інакше LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Наведіть стрілку на max (LCS (i-1) ( j), LCS (i) (j-1))

Приклади Python, Java та 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); )