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 się, ż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.
Przykład:
tekst: ZZXZZY wzorzec: ZZY
Iteracja 1
“! “! “!
tekst Z Z X Z Z Y
wzorzec Z Z Y
Ä™! Ä™! Ä™!
Iteracja 2
“! “!
tekst Z Z X Z Z Y
wzorzec Z Z Y
Ä™! Ä™!
Iteracja 3
“!
tekst Z Z X Z Z Y
wzorzec Z Z Y
Ä™!
Iteracja 4
“! “! “!
tekst Z Z X Z Z Y
wzorzec Z Z Y
Ä™! Ä™! Ä™!
Znaleziono rozwiÄ…zanie: Wzorzec zaczyna siÄ™ od indeksu 3.
4. Zadania do wykonania:
Proszę napisać:
" funkcję, która znajduje długość łańcucha:
int długosc(char*lan);
" funkcję, która sprawdza, czy dany wzorzec wystąpił w tekście. Jeśli tak, to zwraca indeks od
którego zaczyna się wzorzec w tekście lub -1:
int sprawdz(char*tekst, char*wzor);
" funkcję, która znajduje wszystkie wzorce występujące w tekście, zwraca wskaz
nik do tablicy
indeksów (wewnątrz funkcji dynamiczna rezerwacja pamięci dla tablicy indeksów) oraz
udostępnia ich ilość przez wskaz
nik :
int* sprawdz_w(char* tekst, char * wzor, int* ilosc);
" funkcję main, w której należy wczytać dwa dowolne łańcuchy, wywołać funkcję sprawdz i
wypisać wynik (czy znaleziono wzorzec, jeśli tak, to od jakiego indeksu się zaczyna). Jeśli
znaleziono wzorzec, należy wywołać funkcję sprawdz_w i również wypisać odpowiednie wyniki
(ilość znalezionych wzorców i ich indeksy). Operacje: wczytania łańcuchów, wywołania funkcji i
wypisywania wyników przeprowadzać dopóki wzorzec znajduje się w tekście.