Nejdelší společná podposloupnost

O(m·n)

Podposloupnost zachovává pořadí znaků, ale dovolí kterýkoli vynechat; nejdelší společná podposloupnost (LCS) je ta nejdelší sdílená oběma řetězci. Tabulka dp[i][j] uchovává délku LCS prvních i znaků A a prvních j znaků B. Když se dva znaky shodují, buňka prodlouží diagonálu o jedna; jinak vezme lepší z možností vynechat znak z A nebo z B. Vyplnění tabulky je O(m·n) a pravý dolní roh je výsledek. LCS stojí za nástroji diff, slučováním verzí i zarovnáním sekvencí DNA.

DP tabulka
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Vyplň první řádek a sloupec nulami — jakýkoli řetězec vůči prázdnému nesdílí nic.
  2. Pokud se dva znaky shodují, vezmi hodnotu z diagonály plus jedna.
  3. Jinak vezmi větší z buňky nahoře a buňky vlevo.
  4. Buňka vpravo dole drží délku nejdelší společné podposloupnosti.

Pseudokód

1lcs(a, b):                          # O(m·n)2  dp[i][0] ← 0,  dp[0][j] ← 0        # empty prefix → length 03  for i in 1..m, j in 1..n:4    if a[i-1] = b[j-1]:5      dp[i][j] ← dp[i-1][j-1] + 1    # extend the subsequence6    else:7      dp[i][j] ← max(dp[i-1][j], dp[i][j-1])8  return dp[m][n]