Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.mixmin.net!aioe.org!.POSTED!not-for-mail
From: glen herrmannsfeldt <gah@ugcs.caltech.edu>
Newsgroups: comp.lang.java.programmer
Subject: Re: Patricia trie vs binary search.
Date: Thu, 24 May 2012 23:39:23 +0000 (UTC)
Organization: Aioe.org NNTP Server
Lines: 13
Message-ID: <jpmgrb$o5a$1@speranza.aioe.org>
References: <jpmev4$63l$1@dont-email.me>
NNTP-Posting-Host: H0vc4U5LIRkRHNPyGCs2dA.user.speranza.aioe.org
X-Complaints-To: abuse@aioe.org
User-Agent: tin/1.9.6-20100522 ("Lochruan") (UNIX) (Linux/2.6.32-5-amd64 (x86_64))
X-Notice: Filtered by postfilter v. 0.8.2
Xref: csiph.com comp.lang.java.programmer:14786

markspace <-@.> wrote:
> For some reason I was thinking about sub-string searches today.  I 
> looked up Patricia tries (a kind of radix tree) to see if they would 
> help.  While interesting, the radix tree seems to have a lot of overhead 
> for large numbers of entries.

I am not so sure which substring problem you are interested in,
but you might look at the Aho-Korasick algorithm.

If you want to allow for insertions and/or deletions, look
at dynamic programming.

-- glen