Glede na besedilo txt[0. . . N-1] in vzorec postelja [0 . . . M-1] , napišite funkcijo search(char pat[], char txt[]), ki natisne vse pojavitve pat[] v txt[]. To lahko domnevate n > M .
Primeri:
Priporočena težava Rešite težavoVnos: txt[] = TO JE TESTNO BESEDILO, pat[] = TEST
Izhod: Vzorec najden pri indeksu 10Vnos: txt[] = VAŠI OČETI
pat[] = AABA
Izhod: Vzorec najden pri indeksu 0, vzorec najden pri indeksu 9, vzorec najden pri indeksu 12Prihodi vzorca v besedilu
Razpravljali smo o naivnem algoritmu za iskanje vzorcev v prejšnja objava . Najslabši primer kompleksnosti naivnega algoritma je O(m(n-m+1)). Časovna kompleksnost algoritma KMP je v najslabšem primeru O(n+m).
Iskanje vzorcev KMP (Knuth Morris Pratt):
The Naivni algoritem za iskanje vzorcev ne deluje dobro v primerih, ko vidimo veliko ujemajočih se znakov, ki jim sledi neujemajoči se znak.
Primeri:
1) txt[] = AAAAAAAAAAAAAAAAAAB, pat[] = AAAAB
2) txt[] = ABABABCABABABCABABABC, pat[] = ABABAC (ni najslabši primer, ampak slab primer za Naive)
Algoritem za ujemanje KMP uporablja degenerativno lastnost (vzorec, ki ima iste podvzorce, ki se v vzorcu pojavljajo več kot enkrat) vzorca in izboljša kompleksnost v najslabšem primeru na O(n+m) .
Osnovna ideja KMP-jevega algoritma je: kadarkoli zaznamo neujemanje (po nekaj ujemanjih), že poznamo nekatere znake v besedilu naslednjega okna. Te informacije izkoriščamo, da se izognemo ujemanju znakov, za katere vemo, da se bodo vseeno ujemali.
Pregled ujemanja
txt = AAAAABAAABA
pat = AAAA
Primerjamo prvo okno txt z enakotxt = AAAA OČE
celo = AAAA [Začetni položaj]
Najdemo ujemanje. To je enako kot Naivno ujemanje nizov .V naslednjem koraku primerjamo naslednje okno txt z enako .
txt = AAAAA UNIČITI
celo = AAAA [Vzorec premaknjen za en položaj]Tukaj KMP izvaja optimizacijo namesto Naive. V tem drugem oknu primerjamo le četrti A vzorca
s četrtim znakom trenutnega okna besedila, da se odloči, ali se trenutno okno ujema ali ne. Odkar vemo
prvi trije znaki se bodo vseeno ujemali, ujemanje prvih treh znakov smo preskočili.Potrebujete predhodno obdelavo?
Iz zgornje razlage se pojavi pomembno vprašanje, kako vedeti, koliko znakov je treba preskočiti. Da bi vedel to,
predhodno obdelamo vzorec in pripravimo niz celih števil lps[], ki nam pove število znakov, ki jih je treba preskočiti
Pregled predhodne obdelave:
- Algoritem KMP vnaprej obdela pat[] in izdela pomožni element lps[] velikosti m (enako kot velikost vzorca), ki se uporablja za preskakovanje znakov med ujemanjem.
- Ime lps označuje najdaljšo pravilno predpono, ki je tudi pripona. Pravilna predpona je predpona s celim nizom, ki ni dovoljena. Na primer, predpone ABC so , A, AB in ABC. Pravilne predpone so , A in AB. Pripone niza so , C, BC in ABC.
- Iščemo lps v podvzorcih. Jasneje se osredotočamo na podnize vzorcev, ki so hkrati predpona in pripona.
- Za vsak podvzorec pat[0..i], kjer je i = 0 do m-1, lps[i] shrani dolžino največje ujemajoče se ustrezne predpone, ki je tudi pripona podvzorca pat[0..i ].
lps[i] = najdaljša pravilna predpona pat[0..i], ki je tudi pripona pat[0..i].
Opomba: lps[i] bi lahko opredelili tudi kot najdaljšo predpono, ki je tudi pravilna pripona. Uporabiti ga moramo pravilno na enem mestu, da zagotovimo, da ni upoštevan celoten podniz.
Primeri konstrukcije lps[]:
Za vzorec AAAA je lps[] [0, 1, 2, 3]
Za vzorec ABCDE je lps[] [0, 0, 0, 0, 0]
Za vzorec AABACAABAA je lps[] [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
Za vzorec AAACAAAAAC je lps[] [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]
Za vzorec AAABAAA je lps[] [0, 1, 2, 0, 1, 2, 3]
Algoritem predhodne obdelave:
V delu predprocesiranja,
- Vrednosti izračunamo v lps[] . Da bi to naredili, spremljamo dolžino najdaljše vrednosti pripone predpone (uporabljamo samo spremenljivka za ta namen) za prejšnji indeks
- Inicializiramo lps[0] in samo kot 0.
- če pat[len] in postelje ujemanje, povečujemo samo za 1 in povečano vrednost dodelite lps[i].
- Če se pat[i] in pat[len] ne ujemata in len ni 0, posodobimo len na lps[len-1]
- glej computeLPSArray() v spodnji kodi za podrobnosti
Ilustracija predprocesiranja (ali konstrukcije lps[]):
pat[] = AAAAAAA
=> len = 0, i = 0:
- lps[0] je vedno 0, premaknemo se na i = 1
=> len = 0, i = 1:
- Ker se pat[len] in pat[i] ujemata, naredite len++,
- shranite v lps[i] in naredite i++.
- Nastavite len = 1, lps[1] = 1, i = 2
=> len = 1, i = 2:
- Ker se pat[len] in pat[i] ujemata, naredite len++,
- shranite v lps[i] in naredite i++.
- Nastavite len = 2, lps[2] = 2, i = 3
=> len = 2, i = 3:
- Ker se pat[len] in pat[i] ne ujemata in je len> 0,
- Nastavite len = lps[len-1] = lps[1] = 1
=> len = 1, i = 3:
- Ker se pat[len] in pat[i] ne ujemata in je len> 0,
- len = lps[len-1] = lps[0] = 0
=> len = 0, i = 3:
- Ker se pat[len] in pat[i] ne ujemata in je len = 0,
- Nastavite lps[3] = 0 in i = 4
=> len = 0, i = 4:
- Ker se pat[len] in pat[i] ujemata, naredite len++,
- Shranite ga v lps[i] in naredite i++.
- Nastavite len = 1, lps[4] = 1, i = 5
=> len = 1, i = 5:
- Ker se pat[len] in pat[i] ujemata, naredite len++,
- Shranite ga v lps[i] in naredite i++.
- Nastavite len = 2, lps[5] = 2, i = 6
=> len = 2, i = 6:
- Ker se pat[len] in pat[i] ujemata, naredite len++,
- Shranite ga v lps[i] in naredite i++.
- len = 3, lps[6] = 3, i = 7
=> len = 3, i = 7:
- Ker se pat[len] in pat[i] ne ujemata in je len> 0,
- Nastavite len = lps[len-1] = lps[2] = 2
=> len = 2, i = 7:
- Ker se pat[len] in pat[i] ujemata, naredite len++,
- Shranite ga v lps[i] in naredite i++.
- len = 3, lps[7] = 3, i = 8
Tu se ustavimo, saj smo sestavili celoten lps[].
Implementacija algoritma KMP:
Za razliko od Naivni algoritem , kjer vzorec drsimo za eno in primerjamo vse znake pri vsakem premiku, uporabimo vrednost iz lps[], da se odločimo, kateri naslednji znaki se ujemajo. Ideja je, da se ne ujemamo z likom, za katerega vemo, da se bo vseeno ujemal.
Kako uporabiti lps[] za določitev naslednjih položajev (ali vedeti, koliko znakov je treba preskočiti)?
- Primerjavo pat[j] z j = 0 začnemo z znaki trenutnega okna besedila.
- Ohranjamo ujemanje znakov txt[i] in pat[j] ter še naprej povečujemo i in j, medtem ko pat[j] in txt[i] ohranjata ujemanje .
- Ko vidimo a neujemanje
- Vemo, da se znaki pat[0..j-1] ujemajo s txt[i-j…i-1] (upoštevajte, da se j začne z 0 in jo poveča le, če obstaja ujemanje).
- Prav tako vemo (iz zgornje definicije), da je lps[j-1] število znakov v pat[0…j-1], ki so pravilna predpona in pripona.
- Iz zgornjih dveh točk lahko sklepamo, da nam teh znakov lps[j-1] ni treba ujemati s txt[i-j…i-1], ker vemo, da se bodo ti znaki vseeno ujemali. Oglejmo si zgornji primer, da bi to razumeli.
Spodaj je ilustracija zgornjega algoritma:
Razmislite o txt[] = AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA , pat[] = AAAA
Če sledimo zgornjemu postopku gradnje LPS lps[] = {0, 1, 2, 3}
-> i = 0, j = 0: txt[i] in pat[j] se ujemata, naredite i++, j++
-> i = 1, j = 1: txt[i] in pat[j] se ujemata, naredite i++, j++
-> i = 2, j = 2: txt[i] in pat[j] se ujemata, naredite i++, j++
-> i = 3, j = 3: txt[i] in pat[j] se ujemata, naredite i++, j++
-> i = 4, j = 4: Ker je j = M, najden vzorec tiskanja in ponastavitev j, j = lps[j-1] = lps[3] = 3
Tukaj, za razliko od naivnega algoritma, ne ujemamo prvih treh
znakov tega okna. Vrednost lps[j-1] (v zgornjem koraku) nam je dala indeks naslednjega znaka za ujemanje.-> i = 4, j = 3: txt[i] in pat[j] se ujemata, naredite i++, j++
-> i = 5, j = 4: Ker je j == M, najden vzorec tiskanja in ponastavitev j, j = lps[j-1] = lps[3] = 3
Tudi v nasprotju z Naivnim algoritmom se ne ujemamo s prvimi tremi znaki tega okna. Vrednost lps[j-1] (v zgornjem koraku) nam je dala indeks naslednjega znaka za ujemanje.-> i = 5, j = 3: txt[i] in pat[j] se NE ujemata in j> 0, spremenite samo j. j = lps[j-1] = lps[2] = 2
-> i = 5, j = 2: txt[i] in pat[j] se NE ujemata in j> 0, spremenite samo j. j = lps[j-1] = lps[1] = 1
-> i = 5, j = 1: txt[i] in pat[j] se NE ujemata in j> 0, spremenite samo j. j = lps[j-1] = lps[0] = 0
-> i = 5, j = 0: txt[i] in pat[j] se NE ujemata in j je 0, mi delamo i++.
-> i = 6, j = 0: txt[i] in pat[j] se ujemata, naredite i++ in j++
-> i = 7, j = 1: txt[i] in pat[j] se ujemata, naredite i++ in j++
Tako nadaljujemo, dokler v besedilu ni dovolj znakov, ki jih lahko primerjamo z znaki v vzorcu ...
Spodaj je izvedba zgornjega pristopa:
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
> >//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('Najden vzorec ' + 'pri indeksu ' + (i - j) + '
'); j = lps[j - 1]; } // neujemanje po j se ujema z else if (i // Ne ujemajte se z znaki lps[0..lps[j-1]], // vseeno se bodo ujemali, če (j != 0) j = lps[j - 1 ]; else i = i + 1; } } var txt = 'ABABCABAB'; //To kodo je prispeval shruti456rawal> |
>
>
PHP
konstruktor v Javi
// 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('Najden vzorec na indeksu '.($i - $j)); $j = $lps[$j - 1]; } // neujemanje po j se ujema z 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 ?>> |
>
>Izhod
Found pattern at index 10>
Časovna zapletenost: O(N+M), kjer je N dolžina besedila in M dolžina vzorca, ki ga je treba najti.
Pomožni prostor: O(M)