Givet en tekst txt[0 . . . N-1] og et mønster seng[0 . . . M-1] , skriv en funktionssøgning(char pat[], char txt[]), der udskriver alle forekomster af pat[] i txt[]. Det kan du antage N > M .

Eksempler:

Input: txt[] = DETTE ER EN TESTTEKST, pat[] = TEST
Produktion: Mønster fundet ved indeks 10

Input: txt[] = DINE FÆRE
pat[] = AABA
Produktion: Mønster fundet ved indeks 0, Mønster fundet ved indeks 9, Mønster fundet ved indeks 12

Ankomster af mønster i teksten

Vi har diskuteret den naive mønstersøgningsalgoritme i tidligere indlæg . Den værste kompleksitet af den naive algoritme er O(m(n-m+1)). Tidskompleksiteten af ​​KMP-algoritmen er O(n+m) i værste fald.

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

Det Naiv mønstersøgningsalgoritme fungerer ikke godt i tilfælde, hvor vi ser mange matchende karakterer efterfulgt af et mismatchende tegn.

Eksempler:

1) txt[] = AAAAAAAAAAAAAAAAAB, pat[] = AAAAB
2) txt[] = ABABABCABABABCABABABC, pat[] = ABABAC (ikke et værste tilfælde, men et dårligt tilfælde for naiv)

KMP-matchningsalgoritmen bruger degenererende egenskaber (mønster med de samme undermønstre, der optræder mere end én gang i mønsteret) af mønsteret og forbedrer den værst tænkelige kompleksitet til O(n+m) .

ipconfig til ubuntu

Den grundlæggende idé bag KMP's algoritme er: hver gang vi opdager en uoverensstemmelse (efter nogle kampe), kender vi allerede nogle af tegnene i teksten i det næste vindue. Vi udnytter disse oplysninger til at undgå at matche de karakterer, som vi ved vil matche alligevel.

Matchende oversigt

txt = AAAAABAAABA
pat = AAAA
Vi sammenligner første vindue af txt med det samme

txt = AAAA FAR
selv = AAAA [Udgangsposition]
Vi finder et match. Dette er det samme som Naiv String Matching .

I næste trin sammenligner vi næste vindue af txt med det samme .

txt = AAAAA ØDELÆGGE
selv = AAAA [Mønster flyttet en position]

Det er her KMP laver optimering over Naive. I dette andet vindue sammenligner vi kun fjerde A i mønsteret
med fjerde tegn i det aktuelle tekstvindue for at afgøre, om det aktuelle vindue matcher eller ej. Siden vi ved
de første tre tegn vil alligevel matche, vi sprang over at matche de første tre tegn.

Behov for forbehandling?

Et vigtigt spørgsmål opstår fra ovenstående forklaring, hvordan man ved, hvor mange tegn der skal springes over. For at vide dette,
vi forbehandler mønster og forbereder et heltalsarray lps[], der fortæller os antallet af tegn, der skal springes over

Oversigt over forbehandling:

• KMP-algoritmen forbehandler pat[] og konstruerer et hjælpeelement lps[] af størrelse m (samme som størrelsen på mønsteret), som bruges til at springe tegn over, mens de matcher.
• Navn lps angiver det længste egentlige præfiks, som også er et suffiks. Et korrekt præfiks er et præfiks med en hel streng, der ikke er tilladt. For eksempel er præfikser for ABC , A, AB og ABC. Korrekte præfikser er , A og AB. Suffikser af strengen er , C, BC og ABC.
• Vi søger efter lp'er i undermønstre. Mere tydeligt fokuserer vi på understrenge af mønstre, der både er præfiks og suffiks.
• For hvert sub-pattern pat[0..i] hvor i = 0 til m-1, gemmer lps[i] længden af ​​det maksimale matchende korrekte præfiks, som også er et suffiks af sub-pattern pat[0..i] ].

lps[i] = det længste egentlige præfiks af pat[0..i], som også er et suffiks af pat[0..i].

Bemærk: lps[i] kunne også defineres som det længste præfiks, som også er et korrekt suffiks. Vi skal bruge det korrekt på ét sted for at sikre, at hele understrengen ikke tages i betragtning.

Eksempler på lps[]-konstruktion:

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 værdier i lps[] . For at gøre det holder vi styr på længden af ​​den længste præfikssuffiksværdi (vi bruger kun variabel til dette formål) for det foregående indeks
• Vi initialiserer lps[0] og kun som 0.
• Hvis pat[len] og senge match, øger vi kun med 1 og tildel den øgede værdi til lps[i].
• Hvis pat[i] og pat[len] ikke stemmer overens, og len ikke er 0, opdaterer vi len til lps[len-1]
• Se computeLPSArray() i nedenstående kode for detaljer

Illustration af forbehandling (eller konstruktion af lps[]):

pat[] = AAAAAAA

=> len = 0, i = 0:

• lps[0] er altid 0, vi flytter til i = 1

=> len = 0, i = 1:

• Da pat[len] og pat[i] matcher, skal du gøre len++,
• gem det i lps[i] og gør i++.
• Indstil len = 1, lps[1] = 1, i = 2

=> len = 1, i = 2:

• Da pat[len] og pat[i] matcher, skal du gøre len++,
• gem det i lps[i] og gør i++.
• Indstil len = 2, lps[2] = 2, i = 3

=> len = 2, i = 3:

• Da pat[len] og pat[i] ikke stemmer overens, og len> 0,
• Indstil len = lps[len-1] = lps[1] = 1

=> len = 1, i = 3:

• Da pat[len] og pat[i] ikke stemmer overens og len> 0,
• len = lps[len-1] = lps[0] = 0

=> len = 0, i = 3:

• Da pat[len] og pat[i] ikke stemmer overens, og len = 0,
• Indstil lps[3] = 0 og i = 4

=> len = 0, i = 4:

• Da pat[len] og pat[i] matcher, skal du gøre len++,
• Gem det i lps[i] og gør i++.
• Indstil len = 1, lps[4] = 1, i = 5

=> len = 1, i = 5:

• Da pat[len] og pat[i] matcher, skal du gøre len++,
• Gem det i lps[i] og gør i++.
• Indstil len = 2, lps[5] = 2, i = 6

=> len = 2, i = 6:

• Da pat[len] og pat[i] matcher, skal du gøre len++,
• Gem det i lps[i] og gør i++.
• len = 3, lps[6] = 3, i = 7

=> len = 3, i = 7:

• Da pat[len] og pat[i] ikke stemmer overens og len> 0,
• Indstil len = lps[len-1] = lps[2] = 2

=> len = 2, i = 7:

• Da pat[len] og pat[i] matcher, skal du gøre len++,
• Gem det i lps[i] og gør i++.
• len = 3, lps[7] = 3, i = 8

Vi stopper her, da vi har konstrueret hele lp'erne[].

java åben fil

Implementering af KMP-algoritme:

I modsætning til Naiv algoritme , hvor vi glider mønsteret med én og sammenligner alle tegn ved hvert skift, bruger vi en værdi fra lps[] til at bestemme de næste tegn, der skal matches. Ideen er ikke at matche en karakter, som vi ved vil matche alligevel.

Hvordan bruger man lps[] til at bestemme de næste positioner (eller for at kende antallet af tegn, der skal springes over)?

• Vi starter sammenligningen af ​​pat[j] med j = 0 med tegn i det aktuelle tekstvindue.
• Vi bliver ved med at matche tegnene txt[i] og pat[j] og fortsætter med at øge i og j, mens pat[j] og txt[i] beholder matchende .
• Når vi ser en mismatch
  • Vi ved, at tegnene pat[0..j-1] stemmer overens med txt[i-j...i-1] (Bemærk at j starter med 0 og øger det kun, når der er et match).
  • Vi ved også (fra ovenstående definition), at lps[j-1] er antallet af tegn i pat[0...j-1], der både er korrekt præfiks og suffiks.
  • Ud fra de to ovenstående punkter kan vi konkludere, at vi ikke behøver at matche disse lps[j-1]-tegn med txt[i-j...i-1], fordi vi ved, at disse tegn alligevel vil matche. Lad os overveje ovenstående eksempel for at forstå dette.

Nedenfor er illustrationen af ​​ovenstående algoritme:

Overvej txt[] = AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA , klap[] = AAAA

Hvis vi følger ovenstående LPS byggeproces så lps[] = {0, 1, 2, 3}

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

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

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

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

-> i = 4, j = 4: Da j = M, udskriv mønster fundet og nulstil j, j = lps[j-1] = lps[3] = 3

Her i modsætning til naiv algoritme matcher vi ikke de tre første
tegn i dette vindue. Værdien af ​​lps[j-1] (i ovenstående trin) gav os et indeks for næste tegn, der skulle matche.

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

-> i = 5, j = 4: Da j == M, udskriv mønster fundet og nulstil j, j = lps[j-1] = lps[3] = 3
Igen i modsætning til naiv algoritme matcher vi ikke de første tre tegn i dette vindue. Værdien af ​​lps[j-1] (i ovenstående trin) gav os et indeks for næste tegn, der skulle matche.

-> i = 5, j = 3: txt[i] og pat[j] stemmer IKKE overens og j> 0, skift kun j. j = lps[j-1] = lps[2] = 2

-> i = 5, j = 2: txt[i] og pat[j] stemmer IKKE overens og j> 0, skift kun j. j = lps[j-1] = lps[1] = 1

-> i = 5, j = 1: txt[i] og pat[j] stemmer IKKE overens og j> 0, skift kun 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 gør i++.

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

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

Vi fortsætter på denne måde, indtil der er tilstrækkeligt mange tegn i teksten til at blive sammenlignet med tegnene i mønsteret...

Nedenfor er implementeringen af ​​ovenstående tilgang:

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('Fundet mønster ved indeks '.($i - $j));  $j = $lps[$j - 1];  } // mismatch efter j matcher andet hvis ($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 ?>>
 
 
 
 
    
 
>
 
    
 
>
 
  Produktion  
 
Found pattern at index 10>
 
    Tidskompleksitet:    O(N+M) hvor N er længden af ​​teksten og M er længden af ​​det mønster, der skal findes.  
    Hjælpeplads:    O(M)
rudyard kipling hvis forklaring