Gitt en tekst txt[0 . . . N-1] og et mønster seng[0 . . . M-1] , skriv et funksjonssøk(char pat[], char txt[]) som skriver ut alle forekomster av pat[] i txt[]. Du kan anta det N > M .

Eksempler:

Inndata: txt[] = DETTE ER EN TESTTEKST, pat[] = TEST
Produksjon: Mønster funnet ved indeks 10

Inndata: txt[] = DINE FEDRE
klapp[] = AABA
Produksjon: Mønster funnet ved indeks 0, Mønster funnet ved indeks 9, Mønster funnet ved indeks 12

Ankomster av mønster i teksten

Vi har diskutert den naive mønstersøkealgoritmen i forrige innlegg . Den verste tilfelle kompleksiteten til den naive algoritmen er O(m(n-m+1)). Tidskompleksiteten til KMP-algoritmen er O(n+m) i verste fall.

KMP (Knuth Morris Pratt) mønstersøking:

De Naiv mønstersøkealgoritme fungerer ikke bra i tilfeller der vi ser mange samsvarende tegn etterfulgt av et feilaktig tegn.

Eksempler:

1) txt[] = AAAAAAAAAAAAAAAAAAAAB, pat[] = AAAAB
2) txt[] = ABABABABABABABCABABABC, pat[] = ABABAC (ikke et verste tilfelle, men en dårlig sak for naiv)

KMP-tilpasningsalgoritmen bruker degenererende egenskap (mønster som har de samme undermønstrene som vises mer enn én gang i mønsteret) til mønsteret og forbedrer den verste tilfelle kompleksiteten til O(n+m) .

ipconfig for ubuntu

Den grunnleggende ideen bak KMPs algoritme er: hver gang vi oppdager en mismatch (etter noen treff), kjenner vi allerede noen av tegnene i teksten i neste vindu. Vi drar nytte av denne informasjonen for å unngå å matche karakterene som vi vet vil uansett matche.

Matchende oversikt

txt = AAAAABAAABA
pat = AAAA
Vi sammenligner første vindu av tekst med det samme

txt = AAAA FAR
selv = AAAA [Start posisjon]
Vi finner en match. Dette er det samme som Naiv strengmatching .

I neste trinn sammenligner vi neste vindu av tekst med det samme .

txt = AAAAA ØDELEGGE
selv = AAAA [Mønster skiftet én posisjon]

Det er her KMP optimaliserer over Naive. I dette andre vinduet sammenligner vi bare fjerde A av mønsteret
med fjerde tegn i gjeldende tekstvindu for å avgjøre om gjeldende vindu samsvarer eller ikke. Siden vi vet
De tre første tegnene vil uansett samsvare, vi hoppet over å matche de tre første tegnene.

Behov for forbehandling?

Et viktig spørsmål oppstår fra forklaringen ovenfor, hvordan du vet hvor mange tegn som skal hoppes over. For å vite dette,
vi forhåndsbehandler mønster og forbereder en heltallsmatrise lps[] som forteller oss antall tegn som skal hoppes over

Oversikt over forbehandling:

• KMP-algoritmen forbehandler pat[] og konstruerer et hjelpeprogram lps[] av størrelse m (samme som størrelsen på mønsteret) som brukes til å hoppe over tegn mens du matcher.
• Navn lps indikerer det lengste riktige prefikset som også er et suffiks. Et riktig prefiks er et prefiks med en hel streng som ikke er tillatt. For eksempel er prefikser til ABC , A, AB og ABC. Riktige prefikser er , A og AB. Suffiksene til strengen er , C, BC og ABC.
• Vi søker etter lp-er i undermønstre. Mer tydelig fokuserer vi på understrenger av mønstre som er både prefiks og suffiks.
• For hvert sub-pattern pat[0..i] hvor i = 0 til m-1, lagrer lps[i] lengden på det maksimale samsvarende riktige prefikset som også er et suffiks av sub-pattern pat[0..i] ].

lps[i] = det lengste riktige prefikset til pat[0..i] som også er et suffiks av pat[0..i].

Merk: lps[i] kan også defineres som det lengste prefikset som også er et riktig suffiks. Vi må bruke den riktig på ett sted for å sikre at hele delstrengen ikke blir vurdert.

Eksempler på lps[]-konstruksjon:

For mønsteret AAAA er lps[] [0, 1, 2, 3]

For mønsteret ABCDE er lps[] [0, 0, 0, 0, 0]

For mønsteret AABAACAABAA er lps[] [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]

For mønsteret AAACAAAAAC er lps[] [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]

For mønsteret AAABAAA er lps[] [0, 1, 2, 0, 1, 2, 3]

Forbehandlingsalgoritme:

I forbehandlingsdelen,

• Vi beregner verdier i lps[] . For å gjøre det holder vi styr på lengden på den lengste prefikssuffiksverdien (vi bruker bare variabel for dette formålet) for forrige indeks
• Vi initialiserer lps[0] og bare som 0.
• Hvis pat[len] og senger match, øker vi bare med 1 og tilordne den økte verdien til lps[i].
• Hvis pat[i] og pat[len] ikke stemmer overens og len ikke er 0, oppdaterer vi len til lps[len-1]
• Se computeLPSArray() i koden nedenfor for detaljer

Illustrasjon av forbehandling (eller konstruksjon av lps[]):

pat[] = AAAAAAA

=> len = 0, i = 0:

• lps[0] er alltid 0, vi går til i = 1

=> len = 0, i = 1:

• Siden pat[len] og pat[i] samsvarer, gjør len++,
• lagre det i lps[i] og gjør i++.
• Sett len ​​= 1, lps[1] = 1, i = 2

=> len = 1, i = 2:

• Siden pat[len] og pat[i] samsvarer, gjør len++,
• lagre det i lps[i] og gjør i++.
• Sett len ​​= 2, lps[2] = 2, i = 3

=> len = 2, i = 3:

• Siden pat[len] og pat[i] ikke samsvarer, og len> 0,
• Sett len ​​= lps[len-1] = lps[1] = 1

=> len = 1, i = 3:

• Siden pat[len] og pat[i] ikke samsvarer og len> 0,
• len = lps[len-1] = lps[0] = 0

=> len = 0, i = 3:

• Siden pat[len] og pat[i] ikke samsvarer og len = 0,
• Sett lps[3] = 0 og i = 4

=> len = 0, i = 4:

• Siden pat[len] og pat[i] samsvarer, gjør len++,
• Lagre det i lps[i] og gjør i++.
• Sett len ​​= 1, lps[4] = 1, i = 5

=> len = 1, i = 5:

• Siden pat[len] og pat[i] samsvarer, gjør len++,
• Lagre det i lps[i] og gjør i++.
• Sett len ​​= 2, lps[5] = 2, i = 6

=> len = 2, i = 6:

• Siden pat[len] og pat[i] samsvarer, gjør len++,
• Lagre det i lps[i] og gjør i++.
• len = 3, lps[6] = 3, i = 7

=> len = 3, i = 7:

• Siden pat[len] og pat[i] ikke samsvarer og len> 0,
• Sett len ​​= lps[len-1] = lps[2] = 2

=> len = 2, i = 7:

• Siden pat[len] og pat[i] samsvarer, gjør len++,
• Lagre det i lps[i] og gjør i++.
• len = 3, lps[7] = 3, i = 8

Vi stopper her ettersom vi har konstruert hele lp-ene[].

delstrengmetode i java

Implementering av KMP-algoritme:

i motsetning til Naiv algoritme , hvor vi skyver mønsteret med ett og sammenligner alle tegn ved hvert skift, bruker vi en verdi fra lps[] for å bestemme de neste tegnene som skal matches. Tanken er å ikke matche en karakter som vi vet vil uansett matche.

Hvordan bruke lps[] for å bestemme de neste posisjonene (eller for å vite antall tegn som skal hoppes over)?

• Vi starter sammenligningen av pat[j] med j = 0 med tegn i gjeldende tekstvindu.
• Vi fortsetter å matche tegnene txt[i] og pat[j] og fortsetter å øke i og j mens pat[j] og txt[i] holder matchende .
• Når vi ser en misforhold
  • Vi vet at tegnene pat[0..j-1] samsvarer med txt[i-j...i-1] (Merk at j starter med 0 og øker den bare når det er samsvar).
  • Vi vet også (fra definisjonen ovenfor) at lps[j-1] er antall tegn i pat[0...j-1] som er både riktig prefiks og suffiks.
  • Fra de to punktene ovenfor kan vi konkludere med at vi ikke trenger å matche disse lps[j-1]-tegnene med txt[i-j...i-1] fordi vi vet at disse tegnene vil matche uansett. La oss vurdere eksemplet ovenfor for å forstå dette.

Nedenfor er illustrasjonen av algoritmen ovenfor:

Tenk på txt[] = AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA , klapp[] = AAAA

Hvis vi følger ovennevnte LPS byggeprosess da lps[] = {0, 1, 2, 3}

-> i = 0, j = 0: txt[i] og pat[j] samsvarer, gjør i++, j++

-> i = 1, j = 1: txt[i] og pat[j] samsvarer, gjør i++, j++

-> i = 2, j = 2: txt[i] og pat[j] samsvarer, gjør i++, j++

-> i = 3, j = 3: txt[i] og pat[j] samsvarer, gjør i++, j++

-> i = 4, j = 4: Siden j = M, skriv ut mønster funnet og tilbakestill j, j = lps[j-1] = lps[3] = 3

Her i motsetning til naiv algoritme, matcher vi ikke de tre første
tegn i dette vinduet. Verdien av lps[j-1] (i trinnet ovenfor) ga oss indeksen for neste tegn å matche.

-> i = 4, j = 3: txt[i] og pat[j] samsvarer, gjør i++, j++

-> i = 5, j = 4: Siden j == M, skriv ut mønster funnet og tilbakestill j, j = lps[j-1] = lps[3] = 3
Igjen, i motsetning til naiv algoritme, matcher vi ikke de tre første tegnene i dette vinduet. Verdien av lps[j-1] (i trinnet ovenfor) ga oss indeksen for neste tegn å matche.

-> i = 5, j = 3: txt[i] og pat[j] samsvarer IKKE og j> 0, endre bare j. j = lps[j-1] = lps[2] = 2

-> i = 5, j = 2: txt[i] og pat[j] samsvarer IKKE og j> 0, endre bare j. j = lps[j-1] = lps[1] = 1

-> i = 5, j = 1: txt[i] og pat[j] samsvarer IKKE og j> 0, endre bare j. j = lps[j-1] = lps[0] = 0

-> i = 5, j = 0: txt[i] og pat[j] stemmer IKKE overens og j er 0, vi gjør i++.

-> i = 6, j = 0: txt[i] og pat[j] samsvarer, gjør i++ og j++

-> i = 7, j = 1: txt[i] og pat[j] samsvarer, gjør i++ og j++

Vi fortsetter på denne måten til det er nok tegn i teksten til å sammenlignes med tegnene i mønsteret...

Nedenfor er implementeringen av tilnærmingen ovenfor:

C++

>

>

Java

>

>

Python3

>

>

C#

>

>

Javascript

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
  // PHP program for implementation of KMP pattern searching // algorithm // Prints occurrences of txt[] in pat[] function KMPSearch($pat, $txt) {  $M = strlen($pat);  $N = strlen($txt);  // create lps[] that will hold the longest prefix suffix  // values for pattern  $lps=array_fill(0,$M,0);  // Preprocess the pattern (calculate lps[] array)  computeLPSArray($pat, $M, $lps);  $i = 0; // index for txt[]  $j = 0; // index for pat[]  while (($N - $i)>= ($M - $j)) { if ($pat[$j] == $txt[$i]) { $j++;  $i++;  } if ($j == $M) { printf('Funnet mønster ved indeks '.($i - $j));  $j = $lps[$j - 1];  } // mismatch etter j matcher annet if ($i<$N && $pat[$j] != $txt[$i]) {  // Do not match lps[0..lps[j-1]] characters,  // they will match anyway  if ($j != 0)  $j = $lps[$j - 1];  else  $i = $i + 1;  }  } } // Fills lps[] for given pattern pat[0..M-1] function computeLPSArray($pat, $M, &$lps) {  // Length of the previous longest prefix suffix  $len = 0;  $lps[0] = 0; // lps[0] is always 0  // The loop calculates lps[i] for i = 1 to M-1  $i = 1;  while ($i <$M) {  if ($pat[$i] == $pat[$len]) {  $len++;  $lps[$i] = $len;  $i++;  }  else // (pat[i] != pat[len])  {  // This is tricky. Consider the example.  // AAACAAAA and i = 7. The idea is similar  // to search step.  if ($len != 0) {  $len = $lps[$len - 1];  // Also, note that we do not increment  // i here  }  else // if (len == 0)  {  $lps[$i] = 0;  $i++;  }  }  } } // Driver program to test above function  $txt = 'ABABDABACDABABCABAB';  $pat = 'ABABCABAB';  KMPSearch($pat, $txt);   // This code is contributed by chandan_jnu ?>>
 
 
 
 
    
 
>
 
    
 
>
 
  Produksjon  
 
Found pattern at index 10>
 
    Tidskompleksitet:    O(N+M) hvor N er lengden på teksten og M er lengden på mønsteret som skal finnes.  
    Hjelpeplass:    O(M)
rudyard kipling hvis forklaring