W dniu sobota, 12 stycznia 2013 11:05:05 UTC+1 użytkownik M.M. napisał:
> W dniu piątek, 11 stycznia 2013 23:12:26 UTC+1 użytkownik Wojciech Muła napisał:
>
> > W dniu środa, 9 stycznia 2013 21:55:13 UTC+1 użytkownik M.M. napisał:
>
> > > Po drugie, być może potrzebujesz wiele razy wyszukiwać różny wzorzec w
> > > tym samym tekście - wtedy warto zastanowić się nad jakimś zahashowaniem
> > > par (suma,pozycja w tekscie).
>
> > Do takich rzeczy używa się drzew sufiksowych.
>
> Jakie to ma zalety względem hash-table?

Drzewo budujesz raz w czasie O(n). Następnie dowolny wzorzec o długości
m znajdujesz w czasie O(m), a wszystkie jego k wystąpień w czasie
O(k + m).

w.