algorithm
Längsta vanliga efterföljande

Längsta förklaring till vanliga efterföljare

En av de viktigaste implementeringarna av dynamisk programmering är att ta reda på den längsta gemensamma efterföljden . Låt oss först definiera några av de grundläggande terminologierna.

sekvens:

En senare är en sekvens som kan härledas från en annan sekvens genom att radera vissa element utan att ändra ordningen för de återstående elementen. Låt oss säga att vi har en sträng ABC . Om vi raderar noll eller ett eller fler än ett tecken från den här strängen får vi den här strängens efterföljande. Så efterföljderna av strängen ABC kommer att vara { "A" , "B" , "C" , "AB" , "AC" , "BC" , "ABC" , "" }. Även om vi tar bort alla tecken, kommer den tomma strängen också att vara en efterföljande. För att ta reda på efterföljande, för varje tecken i en sträng, har vi två alternativ - antingen tar vi tecknet, eller så gör vi inte. Så om längden på strängen är n finns det 2 ⁿ efterföljder av den strängen.

Längsta vanliga efterföljande:

Som namnet antyder är den längsta vanliga efterföljaren (LCS) av alla vanliga efterföljelser mellan två strängar den med maximal längd. Till exempel: De vanliga sekvenserna mellan "HELLOM" och "HMLD" är "H" , "HL" , "HM" etc. Här är "HLL" den längsta vanliga efterföljaren som har längd 3.

Brute-Force-metod:

Vi kan generera alla sekvenser av två strängar med backtracking . Då kan vi jämföra dem för att ta reda på de vanliga följdarna. Efter det måste vi ta reda på den med maximal längd. Vi har redan sett att det finns 2 ⁿ sekvenser av en sträng med längd n . Det skulle ta år att lösa problemet om vår n korsar 20-25 .

Dynamisk programmeringsmetod:

Låt oss närma oss vår metod med ett exempel. Antag att vi har två strängar abcdaf och acbcf . Låt oss beteckna dessa med s1 och s2 . Så den längsta vanliga efterföljden av dessa två strängar kommer att vara "abcf" , som har längd 4. Återigen påminner jag er, senare behöver inte vara kontinuerliga i strängen. För att konstruera "abcf" ignorerade vi "da" i s1 och "c" i s2 . Hur hittar vi detta med hjälp av dynamisk programmering?

Vi börjar med en tabell (en 2D-grupp) med alla tecken i s1 i rad och alla tecken i s2 i kolumnen. Här är tabellen 0-indexerad och vi lägger tecknen från 1 till och med. Vi går över bordet från vänster till höger för varje rad. Vårt bord kommer att se ut som:

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

Här representerar varje rad och kolumn längden på det längsta vanliga efterföljandet mellan två strängar om vi tar tecknen i den raden och kolumnen och lägger till prefixet före den. Exempel: Tabell [2] [3] representerar längden på den längsta vanliga efterföljden mellan "ac" och "abc" .

Den 0: e kolumnen representerar den tomma efterföljden av s1 . På liknande sätt representerar den 0: e raden den tomma efterföljden av s2 . Om vi tar en tom sekvens av en sträng och försöker matcha den med en annan sträng, oavsett hur lång längd på den andra substansen är, kommer den vanliga efterföljaren att ha 0 längd. Så vi kan fylla i 0: e raderna och 0: e kolumnerna med 0: er. Vi får:

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

Låt oss börja. När vi fyller tabell [1] [1] , frågar vi oss själva, om vi hade en sträng a och en annan sträng a och ingenting annat, vad kommer då att vara det längsta vanliga här? LCS: s längd här är 1. Låt oss nu titta på tabell [1] [2] . Vi har sträng ab och sträng a . LCS-längden kommer att vara 1. Som ni ser kommer resten av värdena att vara 1 för den första raden eftersom den bara betraktar sträng a med abcd , abcda , abcdaf . Så vårt bord kommer att se ut:

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |  1  |  1  |  1  |  1  |  1  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

För rad 2, som nu kommer att inkludera c . För tabell [2] [1] har vi AC på ena sidan och a på den andra sidan. Så LCS-längden är 1. Var fick vi den här från? Uppifrån, som anger LCS a mellan två underlag. Så vad vi säger är att om s1 [2] och s2 [1] inte är samma, kommer LCS-längden att vara den maximala för LCS-längden längst upp eller till vänster . Om du tar längden på LCS längst upp betyder det att vi inte tar det aktuella tecknet från s2 . På samma sätt, om du tar längden på LCS till vänster betyder det att vi inte tar det aktuella tecknet från s1 för att skapa LCS. Vi får:

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |  1  |  1  |  1  |  1  |  1  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |  1  |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

Så vår första formel kommer att vara:

if s2[i] is not equal to s1[j]
    Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif

När vi går vidare för tabell [2] [2] har vi sträng ab och ac . Eftersom c och b inte är samma, lägger vi maximalt upp eller till vänster här. I det här fallet är det igen 1. Därefter har vi för tabell [2] [3] sträng abc och ac . Den här tidens aktuella värden för både rad och kolumn är desamma. Nu kommer LCS-längden att vara lika med den maximala längden på LCS hittills + 1. Hur får vi den maximala längden på LCS hittills? Vi kontrollerar diagonalvärdet, som representerar den bästa matchningen mellan ab och a . Från det här tillståndet, för de aktuella värdena, har vi lagt till ett tecken till s1 och s2 som råkade vara samma. Så LCS-längden kommer naturligtvis att öka. Vi lägger 1 + 1 = 2 i tabell [2] [3] . Vi får,

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |  1  |  1  |  1  |  1  |  1  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |  1  |  1  |  2  |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

Så vår andra formel kommer att vara:

if s2[i] equals to s1[j]
    Table[i][j] = Table[i-1][j-1] + 1
endif

Vi har definierat båda fallen. Med hjälp av dessa två formler kan vi fylla i hela tabellen. När du har fyllt upp bordet ser det ut så här:

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |  1  |  1  |  1  |  1  |  1  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |  1  |  1  |  2  |  2  |  2  |  2  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |  1  |  2  |  2  |  2  |  2  |  2  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |  1  |  2  |  3  |  3  |  3  |  3  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |  1  |  2  |  3  |  3  |  3  |  4  |
     +-----+-----+-----+-----+-----+-----+-----+-----+

LCS-längden mellan s1 och s2 kommer att vara tabell [5] [6] = 4 . Här är 5 och 6 längden på s2 respektive s1 . Vår pseudokod kommer att vara:

Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
    Table[0][i] = 0
endfor
for i from 1 to s2.length
    Table[i][0] = 0
endfor
for i from 1 to s2.length
    for j from 1 to s1.length
        if s2[i] equals to s1[j]
            Table[i][j] = Table[i-1][j-1] + 1
        else
            Table[i][j] = max(Table[i-1][j], Table[i][j-1])
        endif
    endfor
endfor
Return Table[s2.length][s1.length]

Tiden komplexitet för denna algoritm är: O (mn) där m och n anger längden på varje strängar.

Hur tar vi reda på det längsta vanliga efterföljandet? Vi börjar från det nedre högra hörnet. Vi kontrollerar varifrån värdet kommer. Om värdet kommer från diagonalen, det vill säga om tabell [i-1] [j-1] är lika med tabell [i] [j] - 1 , trycker vi på antingen s2 [i] eller s1 [j] (båda är samma) och rör sig diagonalt. Om värdet kommer uppifrån betyder det att om tabell [i-1] [j] är lika med tabell [i] [j] flyttar vi oss till toppen. Om värdet kommer från vänster, betyder det att om tabell [i] [j-1] är lika med tabell [i] [j] flyttar vi till vänster. När vi når den vänstra eller översta kolumnen slutar vår sökning. Sedan popar vi värdena från stacken och skriver ut dem. Pseudokoden:

Procedure PrintLCS(LCSlength, s1, s2)
temp := LCSlength
S = stack()
i := s2.length
j := s1.length
while i is not equal to 0 and j is not equal to 0
     if Table[i-1][j-1] == Table[i][j] - 1 and s1[j]==s2[i]
        S.push(s1[j])   //or S.push(s2[i])
        i := i - 1
        j := j - 1
    else if Table[i-1][j] == Table[i][j]
        i := i-1
    else
        j := j-1
    endif
endwhile
while S is not empty
    print(S.pop)
endwhile

Punkt som bör noteras: om både tabell [i-1] [j] och tabell [i] [j-1] är lika med tabell [i] [j] och tabell [i-1] [j-1] inte är lika med tabell [i] [j] - 1 , det kan finnas två LCS för det ögonblicket. Denna pseudokod beaktar inte denna situation. Du måste lösa detta rekursivt för att hitta flera LCS.

Tidskomplexiteten för denna algoritm är: O (max (m, n)) .