logo

TechCodeview

Algoritmus KMP na vyhľadávanie vzorov

Daný text txt[0. . . N-1] a vzor posteľ[0 . . . M-1] , napíšte funkciu vyhľadávanie (char pat[], char txt[]), ktorá vypíše všetky výskyty pat[] v txt[]. Môžete to predpokladať N > M .

Príklady:



Vstup: txt[] = TOTO JE TESTOVACÍ TEXT, pat[] = TEST
Výkon: Vzor nájdený na indexe 10

Vstup: txt[] = VAŠI OTECKOVIA
pat[] = AABA
Výkon: Vzor nájdený na indexe 0, Vzor nájdený na indexe 9, Vzor nájdený na indexe 12

Príchody vzoru v texte

Príchody vzoru v texte



Odporúčané riešenie problému Problém

Diskutovali sme o naivnom algoritme na vyhľadávanie vzorov v predchádzajúci príspevok . Najhorší prípad zložitosti naivného algoritmu je O(m(n-m+1)). Časová zložitosť KMP algoritmu je v najhoršom prípade O(n+m).

Vyhľadávanie vzorov KMP (Knuth Morris Pratt):

The Naivný algoritmus na vyhľadávanie vzorov nefunguje dobre v prípadoch, keď vidíme veľa zhodných znakov, za ktorými nasleduje nezhodný znak.



Príklady:

1) txt[] = AAAAAAAAAAAAAAAAAAB, pat[] = AAAAB
2) txt[] = ABABABCABABABCABABABC, pat[] = ABABAC (nie najhorší prípad, ale zlý prípad pre naivných)

Algoritmus porovnávania KMP využíva degenerujúcu vlastnosť (vzor s rovnakými podvzormi, ktoré sa vo vzore objavujú viac ako raz) a zlepšuje zložitosť v najhoršom prípade. O(n+m) .

Základná myšlienka algoritmu KMP je: kedykoľvek zistíme nesúlad (po niekoľkých zhodách), už poznáme niektoré znaky v texte nasledujúceho okna. Využívame tieto informácie, aby sme sa vyhli zhode znakov, o ktorých vieme, že sa budú aj tak zhodovať.

Prehľad zhody

txt = AAAAABAAABA
pat = AAAA
Porovnávame prvé okno z TXT s rovnaký

txt = AAAA OTEC
dokonca = AAAA [počiatočná poloha]
Nájdeme zhodu. Toto je rovnaké ako Naivné porovnávanie reťazcov .

V ďalšom kroku porovnáme ďalšie okno TXT s rovnaký .

txt = AAAAA ZNIČIŤ
dokonca = AAAA [Vzor posunutý o jednu pozíciu]

To je miesto, kde KMP robí optimalizáciu oproti Naive. V tomto druhom okne porovnávame iba štvrté A vzoru
so štvrtým znakom aktuálneho okna textu na rozhodnutie, či sa aktuálne okno zhoduje alebo nie. Odkedy vieme
prvé tri znaky sa budú aj tak zhodovať, zhodu prvých troch znakov sme preskočili.

Potrebujete predbežné spracovanie?

Z vyššie uvedeného vysvetlenia vyvstáva dôležitá otázka, ako zistiť, koľko znakov sa má preskočiť. Toto vedieť,
vopred spracujeme vzor a pripravíme celočíselné pole lps[], ktoré nám povie počet znakov, ktoré sa majú preskočiť

Prehľad predbežného spracovania:

  • Algoritmus KMP predspracuje pat[] a vytvorí pomocnú lps[] veľkosti m (rovnaká ako veľkosť vzoru), ktorá sa používa na preskakovanie znakov pri porovnávaní.
  • názov lps označuje najdlhšiu správnu predponu, ktorá je zároveň príponou. Správna predpona je predpona s celým reťazcom, ktorý nie je povolený. Napríklad predpony ABC sú , A, AB a ABC. Správne predpony sú , A a AB. Prípony reťazca sú , C, BC a ABC.
  • Hľadáme lps v podvzorcoch. Jasnejšie sa zameriavame na podreťazce vzorov, ktoré sú predponou aj príponou.
  • Pre každý podvzor pat[0..i], kde i = 0 až m-1, lps[i] ukladá dĺžku maximálnej zodpovedajúcej správnej predpony, ktorá je tiež príponou podvzoru pat[0..i ].

lps[i] = najdlhšia vlastná predpona pat[0..i], ktorá je zároveň príponou pat[0..i].

Poznámka: lps[i] možno definovať aj ako najdlhšiu predponu, ktorá je zároveň správnou príponou. Musíme ho správne použiť na jednom mieste, aby sme sa uistili, že sa neberie do úvahy celý podreťazec.

Príklady konštrukcie lps[]:

Pre vzor AAAA je lps[] [0, 1, 2, 3]

Pre vzor ABCDE je lps[] [0, 0, 0, 0, 0]

Pre vzor AABAACAABAA je lps[] [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]

Pre vzor AAACAAAAAC je lps[] [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]

Pre vzor AAABAAA je lps[] [0, 1, 2, 0, 1, 2, 3]

Algoritmus predbežného spracovania:

V časti predbežného spracovania

  • Vypočítavame hodnoty v lps[] . Aby sme to dosiahli, sledujeme dĺžku najdlhšej hodnoty prípony predpony (používame len premenná na tento účel) pre predchádzajúci index
  • Inicializujeme lps[0] a len ako 0.
  • Ak pat[len] a postele zápas, zvyšujeme len o 1 a priraďte zvýšenú hodnotu lps[i].
  • Ak sa pat[i] a pat[len] nezhodujú a len nie je 0, aktualizujeme len na lps[len-1]
  • Pozri computeLPSArray() podrobnosti nájdete v nižšie uvedenom kóde

Ilustrácia predbežného spracovania (alebo konštrukcie lps[]):

pat[] = AAAAAAA

=> len = 0, i = 0:

  • lps[0] je vždy 0, presunieme sa na i = 1

=> len = 0, i = 1:

  • Keďže pat[len] a pat[i] sa zhodujú, urobte len++,
  • uložte ho do lps[i] a urobte i++.
  • Nastavte len = 1, lps[1] = 1, i = 2

=> len = 1, i = 2:

  • Keďže pat[len] a pat[i] sa zhodujú, urobte len++,
  • uložte ho do lps[i] a urobte i++.
  • Nastavte len = 2, lps[2] = 2, i = 3

=> len = 2, i = 3:

  • Keďže pat[len] a pat[i] sa nezhodujú a len> 0,
  • Nastavte len = lps[len-1] = lps[1] = 1

=> len = 1, i = 3:

  • Keďže pat[len] a pat[i] sa nezhodujú a len> 0,
  • len = lps[len-1] = lps[0] = 0

=> len = 0, i = 3:

  • Keďže pat[len] a pat[i] sa nezhodujú a len = 0,
  • Nastavte lps[3] = 0 a i = 4

=> len = 0, i = 4:

  • Keďže pat[len] a pat[i] sa zhodujú, urobte len++,
  • Uložte to do lps[i] a urobte i++.
  • Nastavte dĺžku = 1, lps[4] = 1, i = 5

=> len = 1, i = 5:

  • Keďže pat[len] a pat[i] sa zhodujú, urobte len++,
  • Uložte to do lps[i] a urobte i++.
  • Nastavte dĺžku = 2, lps[5] = 2, i = 6

=> len = 2, i = 6:

  • Keďže pat[len] a pat[i] sa zhodujú, urobte len++,
  • Uložte to do lps[i] a urobte i++.
  • len = 3, lps[6] = 3, i = 7

=> len = 3, i = 7:

  • Keďže pat[len] a pat[i] sa nezhodujú a len> 0,
  • Nastavte len = lps[len-1] = lps[2] = 2

=> len = 2, i = 7:

  • Keďže pat[len] a pat[i] sa zhodujú, urobte len++,
  • Uložte to do lps[i] a urobte i++.
  • len = 3, lps[7] = 3, i = 8

Tu sa zastavíme, keď sme skonštruovali celý lps[].

Implementácia KMP algoritmu:

Na rozdiel od Naivný algoritmus , kde posúvame vzor o jeden a porovnávame všetky znaky pri každom posune, použijeme hodnotu z lps[] na rozhodnutie o ďalších znakoch, ktoré sa majú zhodovať. Cieľom je nezhodovať sa s postavou, o ktorej vieme, že sa bude aj tak zhodovať.

Ako použiť lps[] na rozhodnutie o ďalších pozíciách (alebo na zistenie počtu znakov, ktoré sa majú preskočiť)?

  • Začneme porovnávanie pat[j] s j = 0 so znakmi aktuálneho okna textu.
  • Udržujeme zhodné znaky txt[i] a pat[j] a neustále zvyšujeme i a j, zatiaľ čo pat[j] a txt[i] zachovávame zhoda .
  • Keď vidíme a nesúlad
    • Vieme, že znaky pat[0..j-1] sa zhodujú s txt[i-j...i-1] (Všimnite si, že j začína nulou a zvyšuje ju iba v prípade zhody).
    • Tiež vieme (z vyššie uvedenej definície), že lps[j-1] je počet znakov pat[0…j-1], ktoré sú správnou predponou aj príponou.
    • Z vyššie uvedených dvoch bodov môžeme usúdiť, že tieto znaky lps[j-1] nemusíme spájať s txt[i-j…i-1], pretože vieme, že tieto znaky sa budú aj tak zhodovať. Pozrime sa na vyššie uvedený príklad, aby sme to pochopili.

Nižšie je ilustrácia vyššie uvedeného algoritmu:

Zvážte txt[] = AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA , pat[] = AAAA

Ak budeme postupovať podľa vyššie uvedeného procesu budovania LPS lps[] = {0, 1, 2, 3}

-> i = 0, j = 0: txt[i] a pat[j] sa zhodujú, urobte i++, j++

-> i = 1, j = 1: txt[i] a pat[j] sa zhodujú, urobte i++, j++

-> i = 2, j = 2: txt[i] a pat[j] sa zhodujú, urobte i++, j++

-> i = 3, j = 3: txt[i] a pat[j] sa zhodujú, urobte i++, j++

-> i = 4, j = 4: Pretože j = M, vzor tlače sa našiel a resetoval j, j = lps[j-1] = lps[3] = 3

Tu na rozdiel od naivného algoritmu nezodpovedáme prvým trom
znaky tohto okna. Hodnota lps[j-1] (v kroku vyššie) nám poskytla index ďalšieho znaku, ktorý sa má zhodovať.

java for loop

-> i = 4, j = 3: txt[i] a pat[j] sa zhodujú, urobte i++, j++

-> i = 5, j = 4: Pretože j == M, vzor tlače sa našiel a resetoval j, j = lps[j-1] = lps[3] = 3
Opäť na rozdiel od naivného algoritmu nezhodujeme prvé tri znaky tohto okna. Hodnota lps[j-1] (v kroku vyššie) nám poskytla index ďalšieho znaku, ktorý sa má zhodovať.

-> i = 5, j = 3: txt[i] a pat[j] sa nezhodujú a j> 0, zmeňte iba j. j = lps[j-1] = lps[2] = 2

-> i = 5, j = 2: txt[i] a pat[j] sa nezhodujú a j> 0, zmeňte iba j. j = lps[j-1] = lps[1] = 1

-> i = 5, j = 1: txt[i] a pat[j] sa nezhodujú a j> 0, zmeňte iba j. j = lps[j-1] = lps[0] = 0

-> i = 5, j = 0: txt[i] a pat[j] sa nezhodujú a j je 0, robíme i++.

-> i = 6, j = 0: txt[i] a pat[j] sa zhodujú, urobte i++ a j++

-> i = 7, j = 1: txt[i] a pat[j] sa zhodujú, urobte i++ a j++

Takto pokračujeme, kým v texte nie je dostatok znakov na porovnanie so znakmi vo vzore...

Nižšie je uvedená implementácia vyššie uvedeného prístupu:

C++




// C++ program for implementation of KMP pattern searching> // algorithm> #include> void> computeLPSArray(>char>* pat,>int> M,>int>* lps);> // Prints occurrences of pat[] in txt[]> void> KMPSearch(>char>* pat,>char>* txt)> {> >int> M =>strlen>(pat);> >int> N =>strlen>(txt);> >// create lps[] that will hold the longest prefix suffix> >// values for pattern> >int> lps[M];> >// Preprocess the pattern (calculate lps[] array)> >computeLPSArray(pat, M, lps);> >int> i = 0;>// index for txt[]> >int> j = 0;>// index for pat[]> >while> ((N - i)>= (M - j)) {> >if> (pat[j] == txt[i]) {> >j++;> >i++;> >}> >if> (j == M) {> >printf>(>'Found pattern at index %d '>, i - j);> >j = lps[j - 1];> >}> >// mismatch after j matches> >else> if> (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] void computeLPSArray(char* pat, int M, int* lps) { // length of the previous longest prefix suffix int len = 0; lps[0] = 0; // lps[0] is always 0 // the loop calculates lps[i] for i = 1 to M-1 int i = 1; while (i 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 code int main() { char txt[] = 'ABABDABACDABABCABAB'; char pat[] = 'ABABCABAB'; KMPSearch(pat, txt); return 0; }> 

>

>

Java




// JAVA program for implementation of KMP pattern> // searching algorithm> class> KMP_String_Matching {> >void> KMPSearch(String pat, String txt)> >{> >int> M = pat.length();> >int> N = txt.length();> >// create lps[] that will hold the longest> >// prefix suffix values for pattern> >int> lps[] =>new> int>[M];> >int> j =>0>;>// index for pat[]> >// Preprocess the pattern (calculate lps[]> >// array)> >computeLPSArray(pat, M, lps);> >int> i =>0>;>// index for txt[]> >while> ((N - i)>= (M - j)) {> >if> (pat.charAt(j) == txt.charAt(i)) {> >j++;> >i++;> >}> >if> (j == M) {> >System.out.println(>'Found pattern '> >+>'at index '> + (i - j));> >j = lps[j ->1>];> >}> >// mismatch after j matches> >else> if> (i && pat.charAt(j) != txt.charAt(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; } } } void computeLPSArray(String pat, int M, int lps[]) { // length of the previous longest prefix suffix int len = 0; int i = 1; lps[0] = 0; // lps[0] is always 0 // the loop calculates lps[i] for i = 1 to M-1 while (i if (pat.charAt(i) == pat.charAt(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] = len; i++; } } } } // Driver code public static void main(String args[]) { String txt = 'ABABDABACDABABCABAB'; String pat = 'ABABCABAB'; new KMP_String_Matching().KMPSearch(pat, txt); } } // This code has been contributed by Amit Khandelwal.> 

>

>

Python3




# Python3 program for KMP Algorithm> def> KMPSearch(pat, txt):> >M>=> len>(pat)> >N>=> len>(txt)> ># create lps[] that will hold the longest prefix suffix> ># values for pattern> >lps>=> [>0>]>*>M> >j>=> 0> # index for pat[]> ># Preprocess the pattern (calculate lps[] array)> >computeLPSArray(pat, M, lps)> >i>=> 0> # index for txt[]> >while> (N>-> i)>>=> (M>-> j):> >if> pat[j]>=>=> txt[i]:> >i>+>=> 1> >j>+>=> 1> >if> j>=>=> M:> >print>(>'Found pattern at index '> +> str>(i>->j))> >j>=> lps[j>->1>]> ># mismatch after j matches> >elif> i and 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 += 1 # Function to compute LPS array def computeLPSArray(pat, M, lps): len = 0 # length of the previous longest prefix suffix lps[0] = 0 # lps[0] is always 0 i = 1 # the loop calculates lps[i] for i = 1 to M-1 while i if pat[i] == pat[len]: len += 1 lps[i] = len i += 1 else: # 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: lps[i] = 0 i += 1 # Driver code if __name__ == '__main__': txt = 'ABABDABACDABABCABAB' pat = 'ABABCABAB' KMPSearch(pat, txt) # This code is contributed by Bhavya Jain> 

>

>

C#




// C# program for implementation of KMP pattern> // searching algorithm> using> System;> class> GFG {> >void> KMPSearch(>string> pat,>string> txt)> >{> >int> M = pat.Length;> >int> N = txt.Length;> >// Create lps[] that will hold the longest> >// prefix suffix values for pattern> >int>[] lps =>new> int>[M];> >// Index for pat[]> >int> j = 0;> >// Preprocess the pattern (calculate lps[]> >// array)> >computeLPSArray(pat, M, lps);> >int> i = 0;> >while> ((N - i)>= (M - j)) {> >if> (pat[j] == txt[i]) {> >j++;> >i++;> >}> >if> (j == M) {> >Console.Write(>'Found pattern '> >+>'at index '> + (i - j));> >j = lps[j - 1];> >}> >// Mismatch after j matches> >else> if> (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; } } } void computeLPSArray(string pat, int M, int[] lps) { // Length of the previous longest prefix suffix int len = 0; int i = 1; lps[0] = 0; // The loop calculates lps[i] for i = 1 to M-1 while (i 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 // len = 0 { lps[i] = len; i++; } } } } // Driver code public static void Main() { string txt = 'ABABDABACDABABCABAB'; string pat = 'ABABCABAB'; new GFG().KMPSearch(pat, txt); } } // This code has been contributed by Amit Khandelwal.> 

>

>

Javascript




panda topiť

> >//Javascript program for implementation of KMP pattern> >// searching algorithm> > >function> computeLPSArray(pat, M, lps)> >{> >// length of the previous longest prefix suffix> >var> len = 0;> >var> i = 1;> >lps[0] = 0;>// lps[0] is always 0> > >// the loop calculates lps[i] for i = 1 to M-1> >while> (i if (pat.charAt(i) == pat.charAt(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] = len; i++; } } } } function KMPSearch(pat,txt) { var M = pat.length; var N = txt.length; // create lps[] that will hold the longest // prefix suffix values for pattern var lps = []; var j = 0; // index for pat[] // Preprocess the pattern (calculate lps[] // array) computeLPSArray(pat, M, lps); var i = 0; // index for txt[] while ((N - i)>= (M - j)) { if (pat.charAt(j) == txt.charAt(i)) { j++; i++; } if (j == M) { document.write('Nájdený vzor ' + 'na indexe ' + (i - j) + ' '); j = lps[j - 1]; } // nezhoda po j sa zhoduje else if (i // Nezhodujú sa znaky lps[0..lps[j-1]], // budú sa aj tak zhodovať, ak (j != 0) j = lps[j - 1 ]; inak i = i + 1 } var txt = 'ABABDABACDABABCABAB'; 

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
  
   // 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('Nájdený vzor v indexe '.($i - $j));  $j = $lps[$j - 1];  } // nezhoda po j sa zhoduje else 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 ?>> 
  
 
    
 
>
 
    
 
>
 
  Výkon  
 
Found pattern at index 10>
 
    Časová zložitosť:    O(N+M), kde N je dĺžka textu a M je dĺžka vzoru, ktorý sa má nájsť.  
    Pomocný priestor:    O(M)