Най-дългата обща последователност

В този урок ще научите как се намира най-дългата обща подпоследователност. Също така ще намерите работни примери за най-дългата обща подпоследователност в 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.label = X Y.label = 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); )