Langste gemeenschappelijke subsequence

Een deelreeks behoudt de volgorde van tekens, maar mag er enkele overslaan. Uit 'abcde' kun je 'ace' nemen, maar nooit 'aec'.

Voor twee tekenreeksen is de langste gemeenschappelijke deelreeks de langste reeks die in beide voorkomt, in dezelfde relatieve volgorde.

Vergelijk voorvoegsels van de twee tekenreeksen. Een tweedimensionale tabel over hun lengtes maakt dit tot een vertrouwde raster-DP.

Laat dp[i][j] de LCS-lengte zijn van de eerste i tekens van A en de eerste j tekens van B.

Als A[i-1] gelijk is aan B[j-1], verlengt die gemeenschappelijke letter de LCS. Tel één op bij de waarde op de diagonaal, dp[i-1][j-1].

Als de letters verschillen, laat je één teken uit een van beide tekenreeksen weg en behoud je het beste resultaat. Neem het maximum van de twee buren.

Een leeg voorvoegsel heeft niets gemeen, dus de LCS-lengte is nul. Rij 0 en kolom 0 blijven volledig gevuld met nullen.

Als je de tabel de afmetingen n+1 bij m+1 geeft, krijg je een gratis rand met nullen. Dat voorkomt vervelende grenscontroles aan de randen.

Doorloop i en j vanaf 1. Elke cel heeft alleen de waarden boven, links en op de diagonaal nodig; die zijn al berekend.

De volledige LCS-lengte staat in de hoek. Het antwoord is dp[n][m] zodra elke cel is ingevuld.

Je bezoekt elke cel één keer, dus het werk kost O(n times m) tijd en geheugen. Daarmee kun je zonder problemen tekenreeksen van enkele duizenden tekens verwerken.

Bouw een tabel van n+1 bij m+1: tel bij een overeenkomst één op bij de diagonaal, en neem anders de maximale buur. In de hoek staat de lengte. 🔗