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 |
©2025 mgr Jerzy Wałaszek |
ProblemW łańcuchu znakowym s należy znaleźć wszystkie wystąpienia wzorca p. |
Problem Wyszukiwania Wzorca – WW (ang. pattern matching) to jeden z podstawowych problemów tekstowych, który intensywnie badali wybitni informatycy. Rozwiązaniem jest wskazanie w ciągu s wszystkich pozycji i takich, że zachodzi równość:
s[i:i+|p|] = p
Oznacza to, iż wzorzec p jest fragmentem łańcucha s występującym na pozycji i-tej.
Algorytm N – naiwny – ustawia okno o długości wzorca
p na pierwszej pozycji
Wszystkie pozycje wzorca p
K01: n ← |s| ; obliczamy długość łańcucha s K02: m ← |p| ; obliczamy długość wzorca p K03: Dla i = 0, 1, …n-m: wykonuj krok K04 K04: Jeśli p = s[i:i+m], ; okno zawiera wzorzec? to pisz i ; jeśli tak, to wypisujemy pozycję K05: 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 60 znakowy łańcuch
zbudowany z pseudolosowych kombinacji liter |
Pascal// Algorytm WWN // Data: 29.05.2008 // (C)2020 mgr Jerzy Wałaszek //--------------------------- program prg; var s, p : ansistring; i : integer; begin randomize; // generujemy łańcuch s := ''; for i := 1 to 60 do s := s+chr(65+random(3)); // generujemy wzorzec p := ''; for i := 1 to 3 do p := p+chr(65+random(3)); // wypisujemy wzorzec writeln(p); // wypisujemy łańcuch writeln(s); // szukamy wzorca w łańcuchu for i := 1 to 58 do if p = copy(s, i, 3) then write('^') else write(' '); writeln; writeln; end. |
// Algorytm WWN // Data: 29.05.2008 // (C)2020 mgr Jerzy Wałaszek //--------------------------- #include <iostream> #include <string> #include <cstdlib> #include <ctime> using namespace std; int main() { string s, p; int i; srand(time(NULL)); // generujemy łańcuch s = ""; for(i = 0; i < 60; i++) s += char(65+(rand() % 3)); // generujemy wzorzec p = ""; for(i = 0; i < 3; i++) p += char(65+(rand() % 3)); // wypisujemy wzorzec cout << p << endl; // wypisujemy łańcuch cout << s << endl; // szukamy wzorca w łańcuchu for(i = 0; i < 58; i++) cout << (p == s.substr(i, 3) ? "^": " "); cout << endl << endl; return 0; } |
Basic' Algorytm WWN ' Data: 29.05.2008 ' (C)2020 mgr Jerzy Wałaszek '--------------------------- Dim As String s, p Dim As Integer i Randomize ' generujemy łańcuch s = "" For i = 1 To 60 s += Chr(65+Cint(Rnd*2)) Next ' generujemy wzorzec p = "" For i = 1 To 3 p += Chr(65+Cint(Rnd*2)) Next ' wypisujemy wzorzec Print p ' wypisujemy łańcuch Print s ' szukamy wzorca w łańcuchu For i = 1 To 58 If p = Mid(s, i, 3) Then Print "^"; Else Print " "; End If Next Print: Print End |
Python
(dodatek)# Algorytm WWN # Data: 6.03.2024 # (C)2024 mgr Jerzy Wałaszek #--------------------------- import random s = "" # łańcuch p = "" # wzorzec # generujemy łańcuch for i in range(60): s += chr(random.randrange(65, 68)) # generujemy wzorzec for i in range(3): p += chr(random.randrange(65, 68)) # wypisujemy wzorzec print(p) # wypisujemy łańcuch print(s) # szukamy wzorca w łańcuchu for i in range(58): if p == s[i:i+3]: print("^", end="") else: print(" ", end="") print() print() |
Wynik: |
ACC CAACCAABCBCAAAABAACCABBBAACCCCACBCACBBABAAABCCABAABCBAABCACC ^ ^ ^ ^ |
Algorytm N możemy nieco usprawnić wykorzystując ideę wartowników. Na końcu łańcucha oraz wzorca umieszczamy dwa różne znaki. Zapobiegną one wyjściu poza obszar łańcucha przy testowaniu znaków w oknie i we wzorcu. Dzięki nim odpadnie sprawdzanie zakresu indeksów w oknie – w efekcie algorytm wykona mniej operacji.
K01: n ← |s| ; obliczamy długość łańcucha s K02: m ← |p| ; obliczamy długość wzorca p K03: s ← s+'X' ; na końcu łańcucha umieszczamy wartownika K04: p ← p+'Y' ; na końcu wzorca umieszczamy innego wartownika K05: Dla i = 0, 1, …, n-m: ; pozycje okna wykonuj kroki K06…K08 K06: j ← 0 ; pozycja w oknie i we wzorcu K07: Dopóki s[i+j] = p[j], ; szukamy pierwszego różnego wykonuj j ← j+1 ; znaku okna i wzorca K08: Jeśli j = m, ; sprawdzamy, czy cały wzorzec to pisz i ; wystąpił w oknie K09: Usuń ostatni znak z s ; pozbywamy się wartownika z łańcucha K10: Usuń ostatni znak z p ; pozbywamy się wartownika ze wzorca K11: 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 60 znakowy łańcuch zbudowany z pseudolosowych kombinacji liter A, B i C. Następnie losuje 3 literowy wzorzec z tych samych liter i algorytmem naiwnym wyszukuje wszystkie wystąpienia wzorca w łańcuchu. Pozycję wzorca zaznacza znakiem ^. |
Pascal// Algorytm WWN z wartownikami // Data: 30.05.2008 // (C)2020 mgr Jerzy Wałaszek //----------------------------- program prg; var s, p : ansistring; i, j : integer; begin randomize; // generujemy łańcuch s := ''; for i := 1 to 60 do s := s+chr(65+random(3)); // generujemy wzorzec p := ''; for i := 1 to 3 do p := p+chr(65+ random(3)); // wypisujemy wzorzec writeln(p); // wypisujemy łańcuch writeln(s); // dodajemy wartowników s := s+'X'; p := p+'Y'; // szukamy wzorca w łańcuchu for i := 1 to 58 do begin j := 0; while s[i+j] = p[j+1] do inc(j); if j = 3 then write('^') else write(' '); end; writeln; writeln; end. |
// Algorytm WWN z wartownikami // Data: 30.05.2008 // (C)2020 mgr Jerzy Wałaszek //---------------------------- #include <iostream> #include <cstdlib> #include <ctime> using namespace std; int main() { string s, p; int i, j; srand(time(NULL)); // generujemy łańcuch s = ""; for(i = 0; i < 60; i++) s += char(65+(rand() % 3)); // generujemy wzorzec p = ""; for(i = 0; i < 3; i++) p += char(65+(rand() % 3)); // wypisujemy wzorzec cout << p << endl; // wypisujemy łańcuch cout << s << endl; // dodajemy wartowników s += "X"; p += "Y"; // szukamy wzorca w łańcuchu for(i = 0; i < 58; i++) { for(j = 0; s[i+j] == p[j]; j++); cout << (j == 3 ? "^" : " "); } cout << endl << endl; return 0; } |
Basic' Algorytm WWN z wartownikami ' Data: 30.05.2008 ' (C)2020 mgr Jerzy Wałaszek '----------------------------- Dim As String s, p Dim As Integer i, j Randomize ' generujemy łańcuch s = "" For i = 1 To 60 s += Chr(65+Cint(Rnd*2)) Next ' generujemy wzorzec p = "" For i = 1 To 3 p += Chr(65+Cint(Rnd*2)) Next ' wypisujemy wzorzec Print p ' wypisujemy łańcuch Print s ' dodajemy wartowników s += "X": p += "Y" ' szukamy wzorca w łańcuchu For i = 1 To 58 j = 0 While Mid(s, i+j, 1) = Mid(p, j+1, 1) j += 1 Wend If j = 3 Then Print "^"; Else Print " "; End If Next Print: Print End |
Python
(dodatek)# Algorytm WWN z wartownikami # Data: 6.03.2024 # (C)2024 mgr Jerzy Wałaszek #--------------------------- import random # generujemy łańcuch s = "" for i in range(60): s += chr(random.randrange(65, 68)) # generujemy wzorzec p = "" for i in range(3): p += chr(random.randrange(65, 68)) # wypisujemy wzorzec print(p) # wypisujemy łańcuch print(s) # dodajemy wartowników s += "X" p += "Y" # szukamy wzorca w łańcuchu for i in range(58): j = 0 while s[i+j:i+j+1] == p[j:j+1]: j += 1 if j == 3: print("^", end="") else: print(" ", end="") print() print() |
Jako ćwiczenie dodaj do programu usuwanie wartowników przed zakończeniem jego pracy.
![]() |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2025 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:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.