Biorąc pod uwagę tekst tekst[0. . . N-1] i wzór łóżko[0 . . . M-1] , napisz funkcję search(char pat[], char txt[]), która wypisuje wszystkie wystąpienia pat[] w txt[]. Możesz to założyć N > M .
Przykłady:
Zalecany problem Rozwiąż problemWejście: txt[] = TO JEST TEKST TESTOWY, pat[] = TEST
Wyjście: Wzór znaleziony w indeksie 10Wejście: txt[] = WASI OJCÓW
pat[] = AABA
Wyjście: Wzór znaleziony pod indeksem 0, Wzór znaleziony pod indeksem 9, Wzór znaleziony pod indeksem 12Przybycie wzorca w tekście
Omówiliśmy naiwny algorytm wyszukiwania wzorców w Poprzedni post . Najgorszy przypadek złożoności algorytmu naiwnego to O(m(n-m+1)). Złożoność czasowa algorytmu KMP w najgorszym przypadku wynosi O(n+m).
Wyszukiwanie wzorców KMP (Knuth Morris Pratt):
The Naiwny algorytm wyszukiwania wzorców nie działa dobrze w przypadkach, gdy widzimy wiele pasujących znaków, po których następuje niedopasowany znak.
Przykłady:
1) txt[] = AAAAAAAAAAAAAAAAB, pat[] = AAAAB
2) txt[] = ABABABCABABABCABABABC, pat[] = ABABAC (nie najgorszy przypadek, ale zły przypadek dla Naiwnego)
Algorytm dopasowywania KMP wykorzystuje właściwość degenerującą (wzór mający te same podwzorce występujące we wzorcu więcej niż raz) wzorca i poprawia złożoność najgorszego przypadku, aby O(n+m) .
Podstawowa idea algorytmu KMP jest następująca: ilekroć wykryjemy niezgodność (po kilku dopasowaniach), znamy już niektóre znaki w tekście następnego okna. Korzystamy z tych informacji, aby uniknąć dopasowywania znaków, o których wiemy, że i tak będą pasować.
Dopasowany przegląd
txt = AAAAABAAABA
klep = AAAA
Porównujemy pierwsze okno tekst z ten samtekst = AAAA OJCIEC
nawet = AAAA [Pozycja początkowa]
Znajdujemy dopasowanie. To jest to samo co Naiwne dopasowywanie ciągów .W kolejnym kroku porównujemy kolejne okno tekst z ten sam .
tekst = AAAAA ZNISZCZYĆ
nawet = AAAA [Wzór przesunięty o jedną pozycję]W tym miejscu KMP dokonuje optymalizacji w stosunku do Naive. W tym drugim oknie porównujemy tylko czwarte A wzoru
z czwartym znakiem bieżącego okna tekstu, aby zdecydować, czy bieżące okno pasuje, czy nie. Skoro wiemy
pierwsze trzy znaki i tak będą pasować, pominęliśmy dopasowywanie pierwszych trzech znaków.Potrzeba wstępnego przetwarzania?
Z powyższego wyjaśnienia wynika ważne pytanie, jak poznać, ile znaków należy pominąć. Aby to wiedzieć,
wstępnie przetwarzamy wzór i przygotowujemy tablicę liczb całkowitych lps[], która informuje nas o liczbie znaków do pominięcia
Przegląd wstępnego przetwarzania:
- Algorytm KMP wstępnie przetwarza pat[] i konstruuje plik pomocniczy lps[] wielkościowy M (taki sam jak rozmiar wzorca), który służy do pomijania znaków podczas dopasowywania.
- Nazwa lps wskazuje najdłuższy właściwy przedrostek, który jest również przyrostkiem. Prawidłowy przedrostek to przedrostek, w którym nie jest dozwolony cały ciąg znaków. Na przykład przedrostki ABC to , A, AB i ABC. Prawidłowe przedrostki to , A i AB. Przyrostki ciągu to , C, BC i ABC.
- Wyszukujemy lps w podwzorach. Bardziej wyraźnie skupiamy się na podciągach wzorców, które są zarówno przedrostkiem, jak i przyrostkiem.
- Dla każdego wzorca podrzędnego [0..i], gdzie i = 0 do m-1, lps[i] przechowuje długość maksymalnie pasującego właściwego przedrostka, który jest również przyrostkiem wzorca podrzędnego [0..i ]
lps[i] = najdłuższy właściwy przedrostek pat[0..i], który jest także przyrostkiem pat[0..i].
Notatka: lps[i] można również zdefiniować jako najdłuższy przedrostek, który jest również właściwym przyrostkiem. Musimy go poprawnie użyć w jednym miejscu, aby mieć pewność, że cały podciąg nie będzie brany pod uwagę.
Przykłady konstrukcji lps[]:
Dla wzorca AAAA lps[] wynosi [0, 1, 2, 3]
Dla wzorca ABCDE lps[] wynosi [0, 0, 0, 0, 0]
Dla wzorca AABAACAABAA lps[] wynosi [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
Dla wzorca AAACAAAAAC, lps[] wynosi [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]
Dla wzorca AAABAAA, lps[] wynosi [0, 1, 2, 0, 1, 2, 3]
Algorytm przetwarzania wstępnego:
W części wstępnej,
- Obliczamy wartości w lps[] . W tym celu śledzimy długość najdłuższej wartości sufiksu przedrostka (używamy tylko zmienna służąca do tego celu) dla poprzedniego indeksu
- Inicjujemy lps[0] I tylko jako 0.
- Jeśli pat[len] I łóżka pasuje, zwiększamy tylko o 1 i przypisz zwiększoną wartość do lps[i].
- Jeśli pat[i] i pat[len] nie pasują, a len nie jest równy 0, aktualizujemy len do lps[len-1]
- Widzieć oblicz tablicę LPS() w poniższym kodzie, aby uzyskać szczegółowe informacje
Ilustracja wstępnego przetwarzania (lub konstrukcji lps[]):
pat[] = AAAAAAA
przechodzenie przez drzewo binarne w kolejności=> dł. = 0, i = 0:
- lps[0] zawsze wynosi 0, przechodzimy do i = 1
=> dł. = 0, i = 1:
- Ponieważ pat[len] i pat[i] pasują, wykonaj len++,
- zapisz go w lps[i] i wykonaj i++.
- Ustaw len = 1, lps[1] = 1, i = 2
=> len = 1, i = 2:
- Ponieważ pat[len] i pat[i] pasują, wykonaj len++,
- zapisz go w lps[i] i wykonaj i++.
- Ustaw len = 2, lps[2] = 2, i = 3
=> len = 2, i = 3:
- Ponieważ pat[len] i pat[i] nie pasują, a len> 0,
- Ustaw len = lps[len-1] = lps[1] = 1
=> len = 1, i = 3:
- Ponieważ pat[len] i pat[i] nie pasują, a len> 0,
- len = lps[len-1] = lps[0] = 0
=> dł. = 0, i = 3:
- Ponieważ pat[len] i pat[i] nie pasują do siebie i len = 0,
- Ustaw lps[3] = 0 i i = 4
=> dł. = 0, i = 4:
- Ponieważ pat[len] i pat[i] pasują, wykonaj len++,
- Zapisz go w lps[i] i wykonaj i++.
- Ustaw len = 1, lps[4] = 1, i = 5
=> dł. = 1, i = 5:
- Ponieważ pat[len] i pat[i] pasują, wykonaj len++,
- Zapisz go w lps[i] i wykonaj i++.
- Ustaw len = 2, lps[5] = 2, i = 6
=> dł. = 2, i = 6:
- Ponieważ pat[len] i pat[i] pasują, wykonaj len++,
- Zapisz go w lps[i] i wykonaj i++.
- len = 3, lps[6] = 3, i = 7
=> dł. = 3, i = 7:
- Ponieważ pat[len] i pat[i] nie pasują, a len> 0,
- Ustaw len = lps[len-1] = lps[2] = 2
=> dł. = 2, i = 7:
- Ponieważ pat[len] i pat[i] pasują, wykonaj len++,
- Zapisz go w lps[i] i wykonaj i++.
- len = 3, lps[7] = 3, i = 8
Zatrzymujemy się tutaj, ponieważ skonstruowaliśmy cały lps[].
Implementacja algorytmu KMP:
w przeciwieństwie do Naiwny algorytm , gdzie przesuwamy wzór o jeden i porównujemy wszystkie znaki przy każdej zmianie, używamy wartości z lps[], aby zdecydować, które kolejne znaki mają zostać dopasowane. Chodzi o to, aby nie dopasowywać postaci, o której wiemy, że i tak będzie pasować.
Jak używać lps[] do określenia kolejnych pozycji (lub poznania liczby znaków do pominięcia)?
- Porównanie pat[j] rozpoczynamy od j = 0 znakami bieżącego okna tekstowego.
- Dopasowujemy znaki txt[i] i pat[j] i zwiększamy i oraz j, podczas gdy pat[j] i txt[i] zachowują dopasowanie .
- Kiedy widzimy A niedopasowanie
- Wiemy, że znaki pat[0..j-1] pasują do txt[i-j…i-1] (Zauważ, że j zaczyna się od 0 i zwiększa je tylko wtedy, gdy występuje dopasowanie).
- Wiemy również (z powyższej definicji), że lps[j-1] to liczba znaków pat[0…j-1], które są zarówno właściwym przedrostkiem, jak i przyrostkiem.
- Z powyższych dwóch punktów możemy wywnioskować, że nie musimy dopasowywać tych znaków lps[j-1] do txt[i-j…i-1], ponieważ wiemy, że te znaki i tak będą pasować. Aby to zrozumieć, rozważmy powyższy przykład.
Poniżej ilustracja powyższego algorytmu:
Rozważ txt[] = AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA , pat[] = AAAA
Jeśli będziemy postępować zgodnie z powyższym procesem budowy LPS lps[] = {0, 1, 2, 3}
-> i = 0, j = 0: txt[i] i pat[j] pasują, wykonaj i++, j++
-> i = 1, j = 1: txt[i] i pat[j] pasują, wykonaj i++, j++
-> i = 2, j = 2: txt[i] i pat[j] pasują, wykonaj i++, j++
-> i = 3, j = 3: txt[i] i pat[j] pasują, wykonaj i++, j++
-> i = 4, j = 4: Ponieważ j = M, wydrukuj wzór i zresetuj j, J = lps[j-1] = lps[3] = 3
Tutaj, w przeciwieństwie do algorytmu Naive, nie dopasowujemy pierwszych trzech
znaków tego okna. Wartość lps[j-1] (w powyższym kroku) dała nam indeks kolejnego pasującego znaku.-> i = 4, j = 3: txt[i] i pat[j] pasują, wykonaj i++, j++
-> i = 5, j = 4: Ponieważ j == M, wypisz wzór i zresetuj j, J = lps[j-1] = lps[3] = 3
Ponownie w przeciwieństwie do algorytmu Naive, nie dopasowujemy pierwszych trzech znaków tego okna. Wartość lps[j-1] (w powyższym kroku) dała nam indeks kolejnego pasującego znaku.-> i = 5, j = 3: txt[i] i pat[j] NIE pasują i j> 0, zmień tylko j. J = lps[j-1] = lps[2] = 2
-> i = 5, j = 2: txt[i] i pat[j] NIE pasują i j> 0, zmień tylko j. J = lps[j-1] = lps[1] = 1
-> i = 5, j = 1: txt[i] i pat[j] NIE pasują i j> 0, zmień tylko j. J = lps[j-1] = lps[0] = 0
-> i = 5, j = 0: txt[i] i pat[j] NIE pasują, a j wynosi 0, robimy i++.
-> i = 6, j = 0: txt[i] i pat[j] pasują, wykonaj i++ i j++
-> i = 7, j = 1: txt[i] i pat[j] pasują, wykonaj i++ i j++
Kontynuujemy w ten sposób, aż w tekście będzie wystarczająca liczba znaków, które można porównać ze znakami we wzorze…
Poniżej implementacja powyższego podejścia:
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; }> |
>
>
Jawa
// 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++; ja++; } if (j == M) { document.write('Znaleziono wzorzec ' + 'at indeks ' + (i - j) + '
'); j = lps[j - 1]; } // niedopasowanie po j pasuje do else if (i // Nie dopasowuj znaków lps[0..lps[j-1]], // i tak będą pasować if (j != 0) j = lps[j - 1 ]; else i = i + 1; } } } var txt = 'ABABDABACDABABCABAB'; var pat = 'ABABCABAB'; KMPSearch(pat, txt); //Ten kod został napisany przez shruti456rawal> |
>
>
PHP
// 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('Znaleziono wzorzec w indeksie '.($i - $j)); $j = $lps[$j - 1]; } // niedopasowanie po j dopasowaniu 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 ?>> |
>
>Wyjście
odwrotny ciąg w Javie
Found pattern at index 10>
Złożoność czasowa: O(N+M) gdzie N to długość tekstu, a M to długość szukanego wzorca.
Przestrzeń pomocnicza: O(M)