[c] liczenie wyrazow

[hellsing]

Dane sa dwa napisy reprezentowane jako ciagi znakow ASCIIZ w tablicazch, przyczym pierwszy(slowo) jest krotszy niz drugi(tekst).

1)napisz procedure w c wyznaczajaca ilosc wystapien slowa w tekscie
2)oblicz zlzonosc obliczeniowa pesymistyczna i optymistyczna zalezna od wuch parametrow m-dlugosc slowa i n-dluosc tekstu.

[matshadow]

1) jak znajdziesz w tekście pierwszą literę słowa, to w forze od 1 do długości słowa sprawdzasz, czy się litery pokrywają. Jak tak, ilość++
w pseudokodzie
tekst w char tekst[], słowo w slowo[]

Kod: Zaznacz cały

bool ok=true;
int il=0;
for(int i=0 to dl_tekstu)
{
       bool ok=true,sp=true;
       if(tekst[i]==slowo[0])
       {
            if(i>0 && tekst[i-1]!=) sp=false;//pamiętaj, że znak poprzedzający słowo to znak interpunkcyjny, ja tylko uwzględniłem spację, chcesz to sobie wyifuj inne możliwości :)
            for(int j=1 to dl_slowa)
              if(slowo[j]!=tekst[i+j])
                ok=false;
            if(ok&&sp) il++;
        }
}

[hellsing]

a co mnie badziej interesuje to jakie sa zlozonosci obliczeniowe tego algorytmu?

[matshadow]

Optymistyczna to \(\displaystyle{ O(n)}\), a pesymistyczna to \(\displaystyle{ O(m\cdot n)}\)