Een tekst gegeven txt[0 . . . N-1] en een patroon bed[0 . . . M-1] , schrijf een functie search(char pat[], char txt[]) die alle voorkomens van pat[] in txt[] afdrukt. Dat mag je aannemen N > M .

Voorbeelden:

Invoer: txt[] = DIT IS EEN TESTTEKST, pat[] = TEST
Uitgang: Patroon gevonden op index 10

Invoer: txt[] = JE VADERS
pat[] = AABA
Uitgang: Patroon gevonden op index 0, patroon gevonden op index 9, patroon gevonden op index 12

Aankomst van patroon in de tekst

We hebben het naïeve algoritme voor het zoeken naar patronen besproken in de vorige post . De worst case complexiteit van het Naïeve algoritme is O(m(n-m+1)). De tijdscomplexiteit van het KMP-algoritme is in het ergste geval O(n+m).

KMP (Knuth Morris Pratt) patroon zoeken:

De Naïef algoritme voor het zoeken naar patronen werkt niet goed in gevallen waarin we veel overeenkomende tekens zien, gevolgd door een niet-overeenkomend teken.

Voorbeelden:

1) txt[] = AAAAAAAAAAAAAAAAAAB, pat[] = AAAAB
2) txt[] = ABABABCABABABCABABABC, pat[] = ABABAC (geen worst case, maar een slecht geval voor Naive)

Het KMP-matchingalgoritme maakt gebruik van de degenererende eigenschap (patroon met dezelfde subpatronen die meer dan eens in het patroon voorkomen) van het patroon en verbetert de worst-case complexiteit om O(n+m) .

Het basisidee achter het algoritme van KMP is: telkens wanneer we een mismatch detecteren (na enkele overeenkomsten), kennen we al enkele karakters in de tekst van het volgende venster. We maken gebruik van deze informatie om te voorkomen dat de tekens overeenkomen waarvan we weten dat ze hoe dan ook overeenkomen.

Matchoverzicht

txt = AAAAABAAABA
pat = AAAAA
We vergelijken het eerste venster van tekst met hetzelfde

txt = AAAA VADER
zelfs = AAAA [Startpositie]
Wij vinden een match. Dit is hetzelfde als Naïeve stringmatching .

In de volgende stap vergelijken we het volgende venster van tekst met hetzelfde .

txt = AAAAA VERNIETIGEN
zelfs = AAAA [Patroon één positie verschoven]

Dit is waar KMP optimalisatie uitvoert boven Naive. In dit tweede venster vergelijken we alleen vierde A van patroon
met het vierde teken van het huidige tekstvenster om te beslissen of het huidige venster overeenkomt of niet. Sinds wij het weten
de eerste drie tekens komen hoe dan ook overeen, we hebben het matchen van de eerste drie tekens overgeslagen.

Voorbewerking nodig?

Uit de bovenstaande uitleg komt een belangrijke vraag naar voren: hoe weet u hoeveel tekens u moet overslaan? Om dit te weten,
we verwerken het patroon vooraf en bereiden een integer-array lps[] voor die ons vertelt hoeveel tekens er moeten worden overgeslagen

Voorverwerkingsoverzicht:

• Het KMP-algoritme verwerkt pat[] voor en bouwt een hulpprogramma lps[] van grootte M (hetzelfde als de grootte van het patroon) dat wordt gebruikt om tekens over te slaan tijdens het matchen.
• Naam lp geeft het langste juiste voorvoegsel aan dat ook een achtervoegsel is. Een correct voorvoegsel is een voorvoegsel waarbij een hele string niet is toegestaan. De voorvoegsels van ABC zijn bijvoorbeeld , A, AB en ABC. De juiste voorvoegsels zijn , A en AB. Achtervoegsels van de string zijn , C, BC en ABC.
• We zoeken naar lps in subpatronen. Het is duidelijker dat we ons concentreren op subreeksen van patronen die zowel voor- als achtervoegsel zijn.
• Voor elk subpatroon pat[0..i] waarbij i = 0 tot m-1, slaat lps[i] de lengte op van het maximaal overeenkomende juiste voorvoegsel dat ook een achtervoegsel is van het subpatroon pat[0..i ].

lps[i] = het langste eigen voorvoegsel van pat[0..i] dat tevens een achtervoegsel is van pat[0..i].

Opmerking: lps[i] kan ook worden gedefinieerd als het langste voorvoegsel, dat ook een echt achtervoegsel is. We moeten het op één plek correct gebruiken om ervoor te zorgen dat niet de hele subtekenreeks in aanmerking wordt genomen.

Voorbeelden van lps[]-constructie:

Voor het patroon AAAA is lps[] [0, 1, 2, 3]

Voor het patroon ABCDE is lps[] [0, 0, 0, 0, 0]

Python sorteert tupels

Voor het patroon AABAACAABAA is lps[] [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]

Voor het patroon AAACAAAAAC is lps[] [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]

Voor het patroon AAABAAA is lps[] [0, 1, 2, 0, 1, 2, 3]

Voorverwerkingsalgoritme:

In het voorbewerkingsgedeelte

• We berekenen waarden in lps[] . Om dat te doen, houden we de lengte bij van de langste voorvoegsel-achtervoegselwaarde (we gebruiken alleen variabele voor dit doel) voor de vorige index
• Wij initialiseren lps[0] En alleen als 0.
• Als pat [len] En bedden overeenkomen, wij verhogen alleen met 1 en wijs de verhoogde waarde toe aan lps[i].
• Als pat[i] en pat[len] niet overeenkomen en len niet 0 is, updaten we len naar lps[len-1]
• Zien berekenenLPSArray() in de onderstaande code voor meer informatie

Illustratie van voorbewerking (of constructie van lps[]):

pat[] = AAAAAAA

=> len = 0, ik = 0:

• lps[0] is altijd 0, we gaan naar i = 1

=> len = 0, ik = 1:

• Omdat pat[len] en pat[i] overeenkomen, doe dan len++,
• sla het op in lps[i] en doe i++.
• Stel len = 1, lps[1] = 1, i = 2 in

=> len = 1, ik = 2:

• Omdat pat[len] en pat[i] overeenkomen, doe dan len++,
• sla het op in lps[i] en doe i++.
• Stel len = 2, lps[2] = 2, i = 3 in

=> len = 2, ik = 3:

• Omdat pat[len] en pat[i] niet overeenkomen, en len> 0,
• Stel len = lps[len-1] = lps[1] = 1 in

=> len = 1, ik = 3:

• Omdat pat[len] en pat[i] niet overeenkomen en len> 0,
• len = lps[len-1] = lps[0] = 0

=> len = 0, ik = 3:

Linux-opdrachten maken map aan

• Omdat pat[len] en pat[i] niet overeenkomen en len = 0,
• Stel lps[3] = 0 en i = 4 in

=> len = 0, ik = 4:

• Omdat pat[len] en pat[i] overeenkomen, doe dan len++,
• Sla het op in lps[i] en voer i++ uit.
• Stel len = 1, lps[4] = 1, i = 5 in

=> len = 1, ik = 5:

• Omdat pat[len] en pat[i] overeenkomen, doe dan len++,
• Sla het op in lps[i] en voer i++ uit.
• Stel len = 2, lps[5] = 2, i = 6 in

=> len = 2, ik = 6:

• Omdat pat[len] en pat[i] overeenkomen, doe dan len++,
• Sla het op in lps[i] en voer i++ uit.
• len = 3, lps[6] = 3, ik = 7

=> len = 3, ik = 7:

• Omdat pat[len] en pat[i] niet overeenkomen en len> 0,
• Stel len = lps[len-1] = lps[2] = 2 in

=> len = 2, ik = 7:

• Omdat pat[len] en pat[i] overeenkomen, doe dan len++,
• Sla het op in lps[i] en voer i++ uit.
• len = 3, lps[7] = 3, ik = 8

We stoppen hier omdat we de hele lps[] hebben gebouwd.

Implementatie van KMP-algoritme:

In tegenstelling tot de Naïef algoritme , waar we het patroon met één verschuiven en alle karakters bij elke verschuiving vergelijken, gebruiken we een waarde uit lps[] om te beslissen welke volgende karakters moeten worden gematcht. Het idee is om een ​​personage waarvan we weten dat het hoe dan ook zal matchen, niet te matchen.

Hoe gebruik ik lps[] om de volgende posities te bepalen (of om te weten hoeveel tekens er moeten worden overgeslagen)?

• We beginnen de vergelijking van pat[j] met j = 0 met karakters van het huidige tekstvenster.
• We blijven de karakters txt[i] en pat[j] matchen en blijven i en j verhogen, terwijl pat[j] en txt[i] behouden blijven bij elkaar passen .
• Wanneer we zien een niet-overeenkomend
  • We weten dat de karakters pat[0..j-1] overeenkomen met txt[i-j…i-1] (merk op dat j begint met 0 en deze alleen verhoogt als er een overeenkomst is).
  • We weten ook (uit de bovenstaande definitie) dat lps[j-1] het aantal tekens van pat[0…j-1] is die zowel een juist voor- als achtervoegsel zijn.
  • Uit de bovenstaande twee punten kunnen we concluderen dat we deze lps[j-1]-tekens niet hoeven te matchen met txt[i-j…i-1] omdat we weten dat deze tekens hoe dan ook zullen matchen. Laten we het bovenstaande voorbeeld bekijken om dit te begrijpen.

Hieronder ziet u de illustratie van het bovenstaande algoritme:

Overweeg txt[] = AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA , pat[] = AAAA

Als we het bovenstaande LPS-bouwproces volgen dan lps[] = {0, 1, 2, 3}

-> ik = 0, j = 0: txt[i] en pat[j] komen overeen, do i++, j++

-> ik = 1, j = 1: txt[i] en pat[j] komen overeen, do i++, j++

-> ik = 2, j = 2: txt[i] en pat[j] komen overeen, do i++, j++

-> ik = 3, j = 3: txt[i] en pat[j] komen overeen, do i++, j++

-> ik = 4, j = 4: Omdat j = M, printpatroon gevonden en j opnieuw ingesteld, J = lps[j-1] = lps[3] = 3

In tegenstelling tot het Naïeve algoritme komen we hier niet overeen met de eerste drie
karakters van dit venster. De waarde van lps[j-1] (in bovenstaande stap) gaf ons de index van het volgende teken dat moest overeenkomen.

-> ik = 4, j = 3: txt[i] en pat[j] komen overeen, do i++, j++

-> ik = 5, j = 4: Omdat j == M, printpatroon gevonden en j opnieuw ingesteld, J = lps[j-1] = lps[3] = 3
Nogmaals, in tegenstelling tot het Naïeve algoritme, komen de eerste drie tekens van dit venster niet overeen. De waarde van lps[j-1] (in bovenstaande stap) gaf ons de index van het volgende teken dat moest overeenkomen.

-> ik = 5, j = 3: txt[i] en pat[j] komen NIET overeen en j> 0, verander alleen j. J = lps[j-1] = lps[2] = 2

-> ik = 5, j = 2: txt[i] en pat[j] komen NIET overeen en j> 0, verander alleen j. J = lps[j-1] = lps[1] = 1

-> ik = 5, j = 1: txt[i] en pat[j] komen NIET overeen en j> 0, verander alleen j. J = lps[j-1] = lps[0] = 0

-> ik = 5, j = 0: txt[i] en pat[j] komen NIET overeen en j is 0, wij doen i++.

-> ik = 6, j = 0: txt[i] en pat[j] komen overeen, i++ en j++

-> ik = 7, j = 1: txt[i] en pat[j] komen overeen, i++ en j++

We gaan zo door totdat er voldoende karakters in de tekst staan ​​om te vergelijken met de karakters in het patroon…

Hieronder vindt u de implementatie van de bovenstaande aanpak:

C++

vijandige zoektocht

>

>

Java

>

>

Python3

math.pow java

>

>

C#

>

>

Javascript

string.bevat Java

>

>

PHP

>

>

Found pattern at index 10>

Tijdcomplexiteit: O(N+M) waarbij N de lengte van de tekst is en M de lengte van het te vinden patroon.
Hulpruimte: O(M)