En samtale mellom en person og en AI-assistent kalt Nordavind [INST] Lag en algoritme for å identifisere den lengste felles delsekvensen i to strenger. Streng A: ABCDGH
Streng B: AEDFHR [/INST]: En enkel løsning på dette problemet vil innebære å opprette en todimensjonal matrise av størrelse (lengden til Streng A + 1) x (lengden til Streng B + 1). Vi fyller gradvis matrisen med verdier ved å iterere over de to strengene. På posisjon (i,j) i matrisen lagrer vi lengden på den lengste delsekvensen av Streng A[0...i] og Streng B[0...j]. Den lengste felles delsekvensen av de to strengene er da verdien lagret på posisjon (lengden til Streng A, lengden til Streng B) i matrisen.