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.

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ć program, który wczytuje dowolny ciąg znaków, znajduje ilość
występowania liter, wypisuje wczytany łańcuch oraz obliczoną ilość liter.

•

Proszę napisać program, który wczytuje dowolny tekst oraz wzorzec. Sprawdza, czy
dany wzorzec wystąpił w tekście. Jeśli tak, to wypisuje indeks od którego zaczyna
się wzorzec w tekście lub informację, że w danym tekście wzorzec nie wystąpił.

•

Proszę zmodyfikować program z punktu wcześniejszego, aby wypisywał ile razy
wzorzec wystąpił w tekście oraz indeksy, od których się zaczynał.