Instrukcja IEF Algorytmy i struktury danych
Laboratorium 1: ”Przeszukiwanie tekstów”.
1.
Wstęp.
Algorytmy przeszukiwania wzorca w tekście słuŜą do odnajdywania w zadanym tekście
określonego ciągu znaków. Ciąg ten moŜe oczywiście występować więcej, niŜ jeden raz.
MoŜliwe jest równieŜ, Ŝe poszukiwany ciąg nie występuje w tekście. W opisie algorytmów
zakłada sie, Ŝe tekst i wzorzec są jednowymiarowymi tablicami znaków, indeksowanymi od
zera.
2.
Informacje wstępne z języka C:
•
deklaracja łańcucha:
char nazwa[rozmiar];
•
wczytanie łańcucha:
gets(nazwa);
fgets(nazwa,rozmiar,stdin);
scanf(”%rozmiar-1[^\n]s”,nazwa);
•
instrukcja warunkowa:
if(warunek)
instrukcja1;
else
instrukcja2;
•
instrukcja pętli:
while(warunek)
instrukcja;
for(wyraŜenie1;wyraŜenie2;wyraŜenie3)
instrukcja;
przykład przeglądania łańcucha znaków:
i=0;
while(nazwa[i]!=’\0’)
{
instrukcja;
i++;
}
for(i=0;nazwa[i]!=’\0’;i++)
instrukcja;
3.
Opis algorytmu naiwnego – brute force
Algorytm ten jest najprostszą metodą na znalezienie wzorca w tekście. Zasada działania opiera
się na porównywaniu odpowiednich liter tekstu i wzorca, zaczynając od pierwszej litery tekstu i
wzorca. Jeśli fragmenty tekstu i wzorca są zgodne, porównywany jest następny znak tekstu z
następnym znakiem wzorca itd. Jeśli wystąpiła niezgodność w dowolnym miejscu – algorytm
rozpoczyna całą procedurę przeszukiwania od drugiego znaku tekstu i pierwszego znaku
wzorca. Jeśli zostanie znaleziony cały szukany wzorzec, algorytm moŜe zakończyć
przeszukiwanie lub rozpocząć je od następnego znaku (tj. wzorzec jest „przesuwany” o jeden
znak).
ZłoŜoność obliczeniowa w najgorszym przypadku wynosi O(N*M), gdzie N jest długością
tekstu, M – długością wzorca.
