Најдужа честа след

У овом упутству ћете научити како се проналази најдужа уобичајена подредница. Такође, наћи ћете радне примере најдуже заједничке подредности у Ц, Ц ++, Јава и Питхон.

Најдужа заједничка подсеквенца (ЛЦС) дефинисана је као најдужа подсеквенца која је заједничка свим датим секвенцама, под условом да елементи подсеквенце нису потребни да заузимају узастопне положаје унутар оригиналних секвенци.

Ако су С1 и С2 две дате секвенце, онда је З заједничка подсеквенца С1 и С2 ако је З подсеквенца и С1 и С2. Даље, З мора бити строго растућа секвенца индекса и С1 и С2.

У строго растућем низу, индекси елемената изабраних из оригиналних секвенци морају бити у растућем редоследу у З.

Ако

 С1 = (Б, Ц, Д, А, А, Ц, Д)

Тада, (A, D, B)не може бити подсеквенца С1 јер редослед елемената није исти (тј. Не стриктно растућа секвенца).

Да разумемо ЛЦС на примеру.

Ако

 С1 = (Б, Ц, Д, А, А, Ц, Д) С2 = (А, Ц, Д, Б, А, Ц)

Тада су уобичајене подсекције (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Међу овим подсеквенцама (C, D, A, C)је и најдужа уобичајена подсеквенца. Пронаћи ћемо ову најдужу заједничку подсеквенцу користећи динамичко програмирање.

Пре него што наставите даље, ако већ не знате динамичко програмирање, прођите кроз динамичко програмирање.

Коришћење динамичког програмирања за проналажење ЛЦС-а

Узмимо две секвенце:

Прва секвенца

Друга секвенца

Следе кораци за проналажење најдуже заједничке подсекције.

Направите табелу димензија n+1*m+1где су н и м дужине Кс, односно И. Први ред и прва колона су испуњени нулама. Иницирајте табелу
Попуните сваку ћелију табеле користећи следећу логику.
Ако се знак који одговара тренутном реду и тренутној колони подудара, испуните тренутну ћелију додавањем једне у дијагонални елемент. Усмерите стрелицу ка дијагоналној ћелији.
Иначе узимају максималну вредност из претходне колоне и претходног елемента реда за попуњавање тренутне ћелије. Усмерите стрелицу на ћелију са максималном вредношћу. Ако су једнаки, покажите на било који од њих. Попуните вредности
Корак 2 се понавља док се табела не попуни. Попуните све вредности
Вредност у последњем реду и последњој колони је дужина најдуже заједничке подредности. Доњи десни угао је дужина ЛЦС-а
Да бисте пронашли најдужу заједничку подсеквенцу, крените од последњег елемента и следите смер стрелице. Елементи који одговарају симболу () чине најдужу заједничку подредност. Направите путању према стрелицама

Дакле, најдужа уобичајена подсекција је ЦД.

ЛЦС

Како је алгоритам динамичког програмирања ефикаснији од рекурзивног алгоритма током решавања ЛЦС проблема?

Метода динамичког програмирања смањује број позива функција. Похрањује резултат сваког позива функције тако да се може користити у будућим позивима без потребе за сувишним позивима.

У горе наведеном динамичком алгоритму, резултати добијени из сваког поређења између елемената Кс и елемената И чувају се у табели како би се могли користити у будућим прорачунима.

Дакле, време потребно динамичком приступу је време потребно за попуњавање табеле (тј. О (мн)). Док алгоритам рекурзије има сложеност од 2 ^{мак (м, н)} .

Најдужи уобичајени алгоритам следова

 Кс и И су две дате секвенце Иницијализујте табелу ЛЦС димензије Кс.ленгтх * И.ленгтх Кс.лабел = Кс И.лабел = И ЛЦС (0) () = 0 ЛЦС () (0) = 0 Старт фром ЛЦС ( 1) (1) Упоредите Кс (и) и И (ј) Ако је Кс (и) = И (ј) ЛЦС (и) (ј) = 1 + ЛЦС (и-1, ј-1) Усмерите стрелицу на ЛЦС (и) (ј) Иначе ЛЦС (и) (ј) = мак (ЛЦС (и-1) (ј), ЛЦС (и) (ј-1)) Усмерите стрелицу на мак (ЛЦС (и-1) ( ј), ЛЦС (и) (ј-1))

Примери за Питхон, Јава и Ц / Ц ++

Питхон Јава Ц Ц ++

 # 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); )