Re: algorytm stringi - Grupy dyskusyjne w eGospodarka.pl

eGospodarka.pl › Grupy › pl.comp.programming › algorytm stringi › Re: algorytm stringi

X-Received: by 10.224.175.65 with SMTP id w1mr420601qaz.7.1357996766405; Sat, 12 Jan
2013 05:19:26 -0800 (PST)
Received: by 10.49.116.115 with SMTP id jv19mr14706326qeb.21.1357996766268; Sat, 12
Jan 2013 05:19:26 -0800 (PST)
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
atman.pl!news.supermedia.pl!plix.pl!newsfeed2.plix.pl!feed.xsnews.nl!border-3.a
ms.xsnews.nl!proxad.net!feeder1-1.proxad.net!198.186.194.247.MISMATCH!news-out.
readnews.com!transit3.readnews.com!209.85.216.88.MISMATCH!p13no1275104qai.0!new
s-out.google.com!k2ni225qap.0!nntp.google.com!p13no1275098qai.0!postnews.google
.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: pl.comp.programming
Date: Sat, 12 Jan 2013 05:19:26 -0800 (PST)
In-Reply-To: <7...@g...com>
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=31.62.66.137;
posting-account=VFwkXwoAAADdT4-lLKRZrMYkTjizGoyn
NNTP-Posting-Host: 31.62.66.137
References: <kceu17$8cf$1@node1.news.atman.pl>
<c...@g...com>
<9...@g...com>
<7...@g...com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <6...@g...com>
Subject: Re: algorytm stringi
From: Wojciech Muła <w...@g...com>
Injection-Date: Sat, 12 Jan 2013 13:19:26 +0000
Content-Type: text/plain; charset=ISO-8859-2
Content-Transfer-Encoding: quoted-printable
Xref: news-archive.icm.edu.pl pl.comp.programming:201646
[ ukryj nagłówki ]

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.