Een deelsequentie van een string S is een geordende reeks karakters, niet noodzakelijk aaneensluitend, uit S. Bv. ‘AGCA’ is een deelsequentie van ‘ATTGCTA’.

Een gemeenschappelijke deelsequentie van twee strings S1 en S2 is een deelsequentie die in beide strings voorkomt. Bv. ‘TTA’ is een gemeenschappelijke deelsequentie van ‘ATCTGAT’ en ‘TGCATA’.

We zoeken een langste gemeenschappelijke deelsequentie* (longest common subsequence, of LCS) van twee strings S1 en S2. Bv. ‘TCTA’ en ‘TGAT’ zijn langste gemeenschappelijke deelsequenties van ‘ATCTGAT’ en ‘TGCATA’.

Opgave

Schrijf een Python functie bepaalLCS die twee strings als parameter krijgt en die een langste gemeenschappelijke deelsequentie van deze strings teruggeeft. De functie moet een algoritme met dynamisch programmeren implementeren.

Voorbeeld

>>> bepaalLCS('ATTTCCTATCCATTTACCACC', 'TTCCATTATCGGTATTAATTACAA')
'TTCCTATCATTTACA'