Serwis Edukacyjny w I-LO w Tarnowie ![]() Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2023 mgr Jerzy Wałaszek |
ProblemW łańcuchu s należy wyznaczyć wszystkie wystąpienia wzorca p. |
Profesor Donald Knuth przeanalizował dokładnie algorytm Morrisa-Pratta i zauważył, iż można go jeszcze ulepszyć. Ulepszenie to polega na nieco innym sposobie wyznaczania tablicy Π w stosunku do algorytmu MP. Otóż oryginalnie tablica ta zawiera maksymalne szerokości prefikso-sufiksów kolejnych prefiksów wzorca. Załóżmy, iż w trakcie porównania dochodzi do niezgodności na pozycji znaku A w łańcuchu przeszukiwanym ze znakiem B we wzorcu (A, B i C oznaczają nie konkretne literki, ale różne znaki łańcucha i wzorca) :
W celu uniknięcia po przesunięciu okna wzorca natychmiastowej niezgodności musimy dodatkowo zażądać, aby znak C leżący tuż za prefikso-sufiksem prefiksu we wzorcu był różny od znaku B, który poprzednio wywołał niezgodność. Algorytm MP nie sprawdzał tej cechy.
Tablicę szerokości prefikso-sufiksów uwzględniającą tę cechę będziemy nazywali tablicą KMPNext. Kolejne jej elementy są maksymalnymi szerokościami prefikso-sufiksów prefiksu wzorca. Jeśli dany prefikso-sufiks nie istnieje (nawet prefikso-sufiks pusty ), to element tablicy ma wartość -1 ( w poprzedniej wersji algorytmu wartownik występował tylko w elemencie o indeksie 0 ).
Przykład:
Wyznaczymy tablicę KMPNext dla wzorca ABACABAB – identyczny wzorzec jak w rozdziale o tworzeniu tablicy Π.
Lp. | Tworzona tablica Next | Opis |
1. |
s : A B A C A B A B i : |
Element KMPNext [ 0 ] jest zawsze równy -1. Pełni on rolę wartownika, dzięki któremu upraszcza się algorytm wyznaczania kolejnych elementów tablicy. |
2. |
s : A B A C A B A B i : 0 1 2 3 4 5 6 7 8 KMPNext[]:-1 0 ? ? ? ? ? ? ? |
Prefiks jednoznakowy A posiada zawsze prefikso-sufiks pusty. Dodatkowo znak A leżący tuż za prefikso-sufiksem oraz znak B leżący za prefiksem są różne. Zatem istnieje prefikso-sufiks pusty o szerokości 0 i to wpisujemy do tablicy. |
3. |
s : A B A C A B A B i : 0 1 2 3 4 5 6 7 8 KMPNext[]:-1 0-1 ? ? ? ? ? ? |
Prefikso-sufiks prefiksu dwuznakowego AB ma szerokość 0. Jednakże znak A leżący tuż za prefikso-sufiksem pustym oraz znak A leżący tuż za prefiksem jest tym samym znakiem. Skoro tak, to prefikso-sufiks nie istnieje - wpisujemy -1. |
4. |
s : A B A C A B A B i : 0 1 2 3 4 5 6 7 8 KMPNext[]:-1 0-1 1 ? ? ? ? ? |
Prefikso-sufiks prefiksu ABA ma szerokość 1 (obejmuje pierwszą i ostatnią literkę A ). Znak B leżący tuż za prefikso-sufiksem oraz znak C leżący za prefiksem są różne. Zatem do tablicy wprowadzamy 1. |
5. |
s : A B A C A B A B i : 0 1 2 3 4 5 6 7 8 KMPNext[]:-1 0-1 1-1 ? ? ? ? |
Prefiks ABAC ma prefikso-sufiks pusty o szerokości 0. Jednakże za prefikso-sufiksem i za prefiksem występuje ten sam znak. Zatem w tablicy umieszczamy -1. |
6. |
s : A B A C A B A B i : 0 1 2 3 4 5 6 7 8 KMPNext[]:-1 0-1 1-1 0 ? ? ? |
Prefiks ABACA posiada prefikso-sufiks o szerokości 1 (pierwsza i ostatnia litera A ). Jednakże za prefikso-sufiksem i prefiksem występuje ten sam znak B. Z tablicy odczytujemy szerokość następnego prefikso-sufiksu - KMPNext [ 1 ] = 0. Jest to prefikso-sufiks pusty. W tym przypadku za prefikso-sufiksem wystąpi litera A, która różni się od litery B za prefiksem. Jest to zatem poszukiwany prefikso-sufiks i szerokość 0 wpisujemy do tablicy. |
7. |
s : A B A C A B A B i : 0 1 2 3 4 5 6 7 8 KMPNext[]:-1 0-1 1-1 0-1 ? ? |
Prefiks ABACAB posiada prefikso-sufiks o szerokości 2 (AB z przodu i z tyłu ). Jednakże za prefikso-sufiksem i za prefiksem występuje ten sam znak A. Odczytujemy z tablicy szerokość następnego prefikso-sufiksu KMPNext [ 2 ] = -1. Prefikso-sufiks nie istnieje, zatem w tablicy umieszczamy -1. |
8. |
s : A B A C A B A B i : 0 1 2 3 4 5 6 7 8 KMPNext[]:-1 0-1 1-1 0-1 3 ? |
Prefiks ABACABA posiada prefikso-sufiks o szerokości 3 ( ABA ). Znak C za prefikso-sufiksem jest różny od znaku B za prefiksem, zatem w tablicy umieszczamy 3. |
9. |
s : A B A C A B A B i : 0 1 2 3 4 5 6 7 8 KMPNext[]:-1 0-1 1-1 0-1 3 2 |
Cały wzorzec ABACABAB posiada prefikso-sufiks o szerokości 2 ( AB ). Ponieważ nie ma już możliwości sprawdzenia znaku A leżącego tuż za prefikso-sufiksem ze znakiem leżącym za wzorcem, to w tablicy umieszczamy 2. Tablica KMPNext jest gotowa. |
Porównajmy tablicę Π
z tablicą KMPNext:
wzorzec | A | B | A | C | A | B | A | B | |
indeks | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Π | -1 | 0 | 0 | 1 | 0 | 1 | 2 | 3 | 2 |
KMPNext | -1 | 0 | -1 | 1 | -1 | 0 | -1 | 3 | 2 |
Algorytm KMP wyszukiwania wzorca wykorzystujący tablicę KMPNext jest identyczny z algorytmem MP wykorzystującym tablicę Π. W algorytmie KMP zastępujemy jedynie odwołania do tablicy Π odwołaniami do tablicy KMPNext [ ], która pozwala bardziej efektywnie wyszukiwać wystąpienia wzorców, ponieważ pomijane są puste przebiegi. Klasa złożoności obliczeniowej jest równa O ( m + n ), gdzie m jest długością wzorca p, a n jest długością przeszukiwanego łańcucha s.
s | – | łańcuch znakowy. |
Tablica KMPNext [ ] z długościami prefikso-sufiksów kolejnych prefiksów łańcucha s. Elementy KMPNext ∈ C.
KMPNext | – | tablica długości prefikso-sufiksów kolejnych prefiksów łańcucha s, KMPNext ∈ C. |
b | – | długość prefikso-sufiksu, b ∈ C. |
i | – | indeks, i ∈ N. |
K01: | KMPNext [ 0 ] ← -1 | na początku tablicy KMPNext wstawiamy wartownika |
K02: | b ← -1 | początkowo długość prefikso-sufiksu ustawiamy na -1 |
K03: | Dla i = 1, 2, ..., |
s |: wykonuj kroki K04...K06 |
wyznaczamy długości prefikso-sufiksów dla prefiksów łańcucha s |
K04: | Dopóki (
b > -1 )
![]() wykonuj b ← KMPNext [ b ] |
w pętli K04 szukamy prefikso-sufiksu b prefiksu wzorca, który da się rozszerzyć. Z pętli wychodzimy, jeśli natrafimy na wartownika lub prefikso-sufiks jest rozszerzalny |
K05: | b ← b + 1 | rozszerzamy prefikso-sufiks |
K06: | Jeśli
i = |s|
![]() to KMPNext [ i ] ← b, inaczej KMPNext [ i ] ← KMPNext [ b ] |
Jeśli następny
znak wzorca różni się od znaku tuż za prefikso-sufiksem, to w tablicy KMPNext umieszczamy szerokość prefikso-sufiksu. Inaczej w KMPNext umieszczamy zredukowaną szerokość prefikso-sufiksu |
K07: | Zakończ |
s | – | łańcuch znakowy |
p | – | poszukiwany wzorzec |
Kolejne pozycje wystąpień wzorca w łańcuchu. Wartość -1 nie wskazuje żadnej pozycji wzorca i oznacza, iż wzorzec nie pojawia się w przeszukiwanym łańcuchu.
pp | – | zawiera wyznaczane pozycje wzorca, pp ∈ C |
i | – | pozycja porównywanego znaku w łańcuchu tekstowym s, i ∈ N, 0 ≤ i ≤ | s | |
b | – | długość prefiksu wzorca p pasującego do prefiksu okna wzorca w łańcuchu s, b ∈ C, 0 ≤ b ≤ | p | |
KMPNext | – | tablica o indeksach od 0 do |p|, przechowująca długości maksymalnych prefikso-sufiksów kolejnych prefiksów wzorca p, KMPNext ∈ C |
K01: | Wyznacz tablicę KMPNext | wyznaczamy tablicę maksymalnych prefikso-sufiksów algorytmem KMP |
K02: | pp ← -1 | wstępna pozycja wzorca ustawiona na -1 |
K03: | b ← 0 | wstępną długość prefikso-sufiksu ustawiamy na 0 |
K04: | Dla i = 0, 1,
... | s | - 1: wykonuj kroki K05...K10 |
pętla wyznacza znaki łańcucha do porównania ze znakami wzorca |
K05: | Dopóki ( b
> -1 )
![]() wykonuj b ← KMPNext [ b ] |
Szukamy we wzorcu p rozszerzalnego prefiksu pasującego do prefiksu okna wzorca. Pętlę K05 przerywamy, jeśli znajdziemy rozszerzalny prefiks lub napotkamy wartownika -1 |
K06: | b ← b + 1 | Rozszerzamy prefiks o 1 znak. Jeśli prefiks był wartownikiem, to otrzymuje wartość 0. |
K07: | Jeśli
b < | p |, to następny obieg pętli K04 |
Jeśli prefiks nie obejmuje całego wzorca, to kontynuujemy pętlę K04, czyli porównujemy znak p [ b ] z kolejnym znakiem łańcucha s. |
K08: | pp ← i - b + 1 | wyznaczamy pozycję wzorca p w łańcuchu s |
K09: | Pisz pp | wyprowadzamy tę pozycję |
K10: | b ← KMPNext [ b ] | redukujemy b do długości prefikso-sufiksu wzorca |
K11: | Jeśli pp = -1, to pisz -1 |
jeśli wzorzec p nie występuje w s, wyprowadzamy -1 |
K12: | Zakończ |
Uwaga:
Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program generuje 79 znakowy łańcuch zbudowany z pseudolosowych kombinacji liter A i B oraz 5 znakowy wzorzec wg tego samego schematu. Następnie program wyznacza tablicę długości maksymalnych prefikso-sufiksów kolejnych prefiksów wzorca i wykorzystuje ją do znalezienia wszystkich wystąpień wzorca w łańcuchu. |
Pascal// Wyszukiwanie wzorca algorytmem KMP // Data: 4.06.2008 // (C)2020 mgr Jerzy Wałaszek //----------------------------- program prg; const N = 79; // długość łańcucha s M = 5; // długość wzorca p var s, p : ansistring; KMPNext : array [ 0..M ] of integer; i, b, pp : integer; begin randomize; // generujemy łańcuch s s := ''; for i := 1 to N do s := s + chr ( 65 + random ( 2 ) ); // generujemy wzorzec p := ''; for i := 1 to M do p := p + chr ( 65 + random ( 2 ) ); // dla wzorca obliczamy tablicę KMPNext [ ] KMPNext [ 0 ] := -1; b := -1; for i := 1 to M do begin while( b > -1 ) and ( p [ b + 1 ] <> p [ i ] ) do b := KMPNext [ b ]; inc ( b ); if( i = M ) or ( p [ i + 1 ] <> p [ b + 1 ] ) then KMPNext [ i ] := b else KMPNext [ i ] := KMPNext [ b ]; end; // wypisujemy wzorzec p writeln ( p ); // wypisujemy łańcuch s writeln ( s ); // poszukujemy pozycji wzorca w łańcuchu pp := 0; b := 0; for i := 1 to N do begin while( b > -1 ) and ( p [ b + 1 ] <> s [ i ] ) do b := KMPNext [ b ]; inc ( b ); if b = M then begin while pp < i - b do begin write ( ' ' ); inc ( pp ); end; write ( '^' ); inc ( pp ); b := KMPNext [ b ]; end end; writeln; end. |
C++// Wyszukiwanie wzorca algorytmem KMP // Data: 4.06.2008 // (C)2020 mgr Jerzy Wałaszek //----------------------------- #include <iostream> #include <string> #include <cstdlib> #include <time.h> using namespace std; const int N = 79; // długość łańcucha s const int M = 5; // długość wzorca p int main( ) { string s, p; int KMPNext [ M + 1 ], i, b, pp; srand ( ( unsigned )time ( NULL ) ); // generujemy łańcuch s s = ""; for( i = 0; i < N; i++ ) s += 65 + rand( ) % 2; // generujemy wzorzec p = ""; for( i = 0; i < M; i++ ) p += 65 + rand( ) % 2; // dla wzorca obliczamy tablicę Next [ ] KMPNext [ 0 ] = b = -1; for( i = 1; i <= M; i++ ) { while( ( b > -1 ) && ( p [ b ] != p [ i - 1 ] ) ) b = KMPNext [ b ]; ++b; if( ( i == M ) || ( p [ i ] != p [ b ] ) ) KMPNext [ i ] = b; else KMPNext [ i ] = KMPNext [ b ]; } // wypisujemy wzorzec cout << p << endl; // wypisujemy łańcuch s cout << s << endl; // poszukujemy pozycji wzorca w łańcuchu pp = b = 0; for( i = 0; i < N; i++ ) { while( ( b > -1 ) && ( p [ b ] != s [ i ] ) ) b = KMPNext [ b ]; if( ++b == M ) { while( pp < i - b + 1 ) { cout << " "; pp++; } cout << "^"; pp++; b = KMPNext [ b ]; } } cout << endl; return 0; } |
Basic' Wyszukiwanie wzorca algorytmem KMP ' Data: 4.06.2008 ' (C)2020 mgr Jerzy Wałaszek '----------------------------- Const N = 79 ' długość łańcucha s Const M = 5 ' długość wzorca p Dim As String s, p Dim As Integer KMPNext ( M ), i, b, pp Randomize ' generujemy łańcuch s s = "" For i = 1 To N: s += Chr ( 65 + Cint ( Rnd ) ): Next ' generujemy wzorzec p = "" For i = 1 To M: p += Chr ( 65 + Cint ( Rnd ) ): Next ' dla wzorca obliczamy tablicę PI [ ] KMPNext ( 0 ) = -1: b = -1 For i = 1 To M while( b > -1 ) And ( Mid ( p, b + 1, 1 ) <> Mid ( p, i, 1 ) ): b = KMPNext ( b ): Wend b += 1: if( i = M ) Or ( Mid ( p, i + 1, 1 ) <> Mid ( p, b + 1, 1 ) ) Then KMPNext ( i ) = b Else KMPNext ( i ) = KMPNext ( b ) End If Next ' wypisujemy wzorzec p Print p ' wypisujemy łańcuch s Print s ' poszukujemy pozycji wzorca w łańcuchu pp = 0: b = 0 For i = 1 To N while( b > -1 ) And ( Mid ( p, b + 1, 1 ) <> Mid ( s, i, 1 ) ): b = KMPNext ( b ): Wend b += 1 If b = M Then While pp < i - b Print " ";: pp += 1 Wend Print "^";: pp += 1 b = KMPNext ( b ) End If Next Print End |
Wynik: |
BABBB AABABBBBABBBBABABAAABBBAABBBABABBABABBAABABBBBBAABAAAAAAABABBBABBBABAABBBBAAAAB ^ ^ ^ ^ ^ |
![]() |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2023 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.