kolejna porcja zadań do mnie dotarła i z dwoma mam problem. Oto one:
Zadanie 11 Dopasowanie wzorca
Dane sa łancuch S[1..n] i wzorzec P[0 ..m − 1], gdzie 1 <= m <= n. Ponizszy
algorytm wyznacza pozycje L wystepowania wzorca P w łancuchu S, tzn.
L = p jesli S[p .. p + m − 1] = P, a L = n − m + 1 jesli wzorzec P nie jest
podciagiem S.
Kod: Zaznacz cały
Dopasuj(P, S, m, n)
1 L <- 0
2 dopasowano <- false
3 while L<= n − m ^ ¬dopasowano
4 do L<-L+ 1
5 r <- 0
6 dopasowano <- true
7 while r < m ^ dopasowano
8 do dopasowano <- (P[r] = S[L + r])
9 r <- r + 1
10 return L
powyzszy algorytm w przypadku pesymistycznym?
drugie:
Algorytm wyznacza yz, gdzie y, z należy do N.
Kod: Zaznacz cały
Mnóz(y, z)
1 if z = 0
2 then return 0
3 else if odd(z)
4 then return Mnóz(2 · y, [z/2]) + y
5 else return Mnóz(2 · y, [z/2])
Z góry dziękuje, za wszelakie podpowiedzi które naprowadza na rozwiązanie.