Naive pattern matching - algorytm, analiza, przyklady krok po kroku
ð Podstawa programowa: I.2bMamy dany tekst T (dlugosci n) i wzorzec W (dlugosci m). Szukamy wszystkich pozycji w tekscie, w ktorych zaczyna sie wzorzec. To dokladnie to, co robi funkcja "Znajdz" (Ctrl+F) w edytorze tekstu!
Najprostrze podejscie: przykladadmy wzorzec do kazdej pozycji tekstu i sprawdzamy znak po znaku, czy pasuje.
ALGORYTM WyszukajNaiwnie(T, W):
n = dlugosc(T)
m = dlugosc(W)
DLA i OD 0 DO n - m:
j = 0
DOPOKI j < m ORAZ T[i + j] = W[j]:
j = j + 1
JESLI j = m:
Wypisz "Wzorzec znaleziony na pozycji " + iTekst: A B A B A C
Wzorzec: A B A C
i=0: A B A B (porownujemy z A B A C)
A=A, B=B, A=A, B!=C -> niezgodnosc na poz. 3
i=1: . B A B A (porownujemy z A B A C)
B!=A -> niezgodnosc na poz. 0
i=2: . . A B A C (porownujemy z A B A C)
A=A, B=B, A=A, C=C -> ZNALEZIONO na pozycji 2!
Wynik: Wzorzec "ABAC" znaleziony na pozycji 2.Uzyj metody naiwnej, aby znalezc wszystkie pozycje wzorca w tekscie. Zapisz kazda probe:
a) T = "ABCABCABC", W = "BCA"
b) T = "AAAAAAA", W = "AAA"
c) T = "INFORMATYKA", W = "MAT"
a) T="ABCABCABC", W="BCA" (n=9, m=3)
i=0: ABC vs BCA -> A!=B, nie
i=1: BCA vs BCA -> B=B, C=C, A=A -> ZNALEZIONO poz. 1
i=2: CAB vs BCA -> C!=B, nie
i=3: ABC vs BCA -> A!=B, nie
i=4: BCA vs BCA -> B=B, C=C, A=A -> ZNALEZIONO poz. 4
i=5: CAB vs BCA -> C!=B, nie
i=6: ABC vs BCA -> A!=B, nie
Wynik: pozycje 1, 4
b) T="AAAAAAA", W="AAA" (n=7, m=3)
i=0: AAA=AAA -> ZNALEZIONO poz. 0
i=1: AAA=AAA -> ZNALEZIONO poz. 1
i=2: AAA=AAA -> ZNALEZIONO poz. 2
i=3: AAA=AAA -> ZNALEZIONO poz. 3
i=4: AAA=AAA -> ZNALEZIONO poz. 4
Wynik: pozycje 0, 1, 2, 3, 4
c) T="INFORMATYKA", W="MAT" (n=11, m=3)
i=0: INF vs MAT -> I!=M, nie
i=1: NFO vs MAT -> N!=M, nie
i=2: FOR vs MAT -> F!=M, nie
i=3: ORM vs MAT -> O!=M, nie
i=4: RMA vs MAT -> R!=M, nie
i=5: MAT vs MAT -> M=M, A=A, T=T -> ZNALEZIONO poz. 5
i=6: ATY vs MAT -> A!=M, nie
i=7: TYK vs MAT -> T!=M, nie
i=8: YKA vs MAT -> Y!=M, nie
Wynik: pozycja 5Ile operacji porownania znakow wykona algorytm naiwny dla:
a) T = "ABCDEF", W = "DEF"
b) T = "AAAAAB", W = "AAB"
a) T="ABCDEF", W="DEF"
i=0: A!=D (1 porownanie)
i=1: B!=D (1 porownanie)
i=2: C!=D (1 porownanie)
i=3: D=D, E=E, F=F (3 porownania) -> znaleziono
Razem: 6 porownan
b) T="AAAAAB", W="AAB"
i=0: A=A, A=A, A!=B (3 porownania)
i=1: A=A, A=A, A!=B (3 porownania)
i=2: A=A, A=A, A!=B (3 porownania)
i=3: A=A, A=A, B=B (3 porownania) -> znaleziono
Razem: 12 porownan
(To najgorszy przypadek - za kazdym razem
porownujemy prawie caly wzorzec!)Zmodyfikuj pseudokod algorytmu naiwnego, aby:
a) Zwracal tylko PIERWSZE wystapienie wzorca (lub -1 jesli nie znaleziono)
b) Zwracal LICZBE wystapien wzorca w tekscie
a) Pierwsze wystapienie:
ALGORYTM PierwszeWystapienie(T, W):
n = dlugosc(T), m = dlugosc(W)
DLA i OD 0 DO n - m:
j = 0
DOPOKI j < m ORAZ T[i+j] = W[j]:
j = j + 1
JESLI j = m:
ZWROC i // znalezione - konczymy!
ZWROC -1 // nie znaleziono
b) Liczba wystapien:
ALGORYTM LiczbaWystapien(T, W):
n = dlugosc(T), m = dlugosc(W)
licznik = 0
DLA i OD 0 DO n - m:
j = 0
DOPOKI j < m ORAZ T[i+j] = W[j]:
j = j + 1
JESLI j = m:
licznik = licznik + 1
ZWROC licznikNapisz pseudokod algorytmu "Znajdz i zamien", ktory w tekscie T zamienia wszystkie wystapienia wzorca W na tekst Z. Przyklad: T="kot i kot", W="kot", Z="pies" -> wynik: "pies i pies".
ALGORYTM ZnajdzIZamien(T, W, Z):
n = dlugosc(T), m = dlugosc(W)
wynik = ""
i = 0
DOPOKI i <= n - m:
// Sprawdz czy wzorzec pasuje na pozycji i
j = 0
DOPOKI j < m ORAZ T[i+j] = W[j]:
j = j + 1
JESLI j = m:
// Wzorzec znaleziony - wstaw zamiennik
wynik = wynik + Z
i = i + m // przeskocz wzorzec
W PRZECIWNYM RAZIE:
wynik = wynik + T[i]
i = i + 1
// Dodaj pozostale znaki
DOPOKI i < n:
wynik = wynik + T[i]
i = i + 1
ZWROC wynik
Test: T="kot i kot", W="kot", Z="pies"
i=0: "kot"="kot" -> wynik="pies", i=3
i=3: " "!="k" -> wynik="pies ", i=4
i=4: "i"!="k" -> wynik="pies i", i=5
i=5: " "!="k" -> wynik="pies i ", i=6
i=6: "kot"="kot" -> wynik="pies i pies", i=9
Wynik: "pies i pies" (poprawnie!)