Groups > comp.lang.java.programmer > #10809

Re: Fast String search algorithm

Path	csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!gegeweb.org!de-l.enfer-du-nord.net!feeder1.enfer-du-nord.net!feeder.erje.net!news-1.dfn.de!news.dfn.de!cache.uni-koblenz.de!not-for-mail
From	Tassilo Horn <tassilo@member.fsf.org>
Newsgroups	comp.lang.java.programmer
Subject	Re: Fast String search algorithm
Date	Fri, 16 Dec 2011 20:07:25 +0100
Organization	University Koblenz-Landau Campus Koblenz
Lines	25
Message-ID	<87r504s5ci.fsf@thinkpad.tsdh.de> (permalink)
References	<i02ne7ptvvl8ofv9uracdu2jm3oq61v2h3@4ax.com>
NNTP-Posting-Host	91-67-11-43-dynip.superkabel.de
Mime-Version	1.0
Content-Type	text/plain
X-Trace	cache.uni-koblenz.de 1324062446 30966 91.67.11.43 (16 Dec 2011 19:07:26 GMT)
X-Complaints-To	news@cache.uni-koblenz.de
NNTP-Posting-Date	Fri, 16 Dec 2011 19:07:26 +0000 (UTC)
User-Agent	Gnus/5.110018 (No Gnus v0.18) Emacs/24.0.92 (gnu/linux)
Cancel-Lock	sha1:UCJwt5ybRyMv04CnMACCyEyG8jY=
Xref	x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:10809

Show key headers only | View raw

Roedy Green <see_website@mindprod.com.invalid> writes:

> Let's say I had a million records each with a text field.  I wanted to
> find all records that contained a given substring.  Are there fast
> algorithms to do that or do you have to scan the whole thing linearly?

Sure.  See http://en.wikipedia.org/wiki/Substring_index

> Similarly, I was wondering how you might build an index to all the
> files on a computer so that you could find one just by giving a wild
> card or partial filename.

On UNIXes, that's exactly what the locate tool does.  Then you can
search with globbing wildcards

  % # all files containing the substring foo
  % locate *foo*

or even with regular expressions

  % # all files that end with "r.c" or "r.cpp"
  % locate -r '.*r\.\(c\|cpp\)$'

Bye,
Tassilo

Thread

Fast String search algorithm Roedy Green <see_website@mindprod.com.invalid> - 2011-12-16 10:08 -0800
  Re: Fast String search algorithm Tom Anderson <twic@urchin.earth.li> - 2011-12-16 18:58 +0000
    Re: Fast String search algorithm markspace <-@.> - 2011-12-17 09:26 -0800
      Re: Fast String search algorithm Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2011-12-17 21:07 -0800
  Re: Fast String search algorithm Tassilo Horn <tassilo@member.fsf.org> - 2011-12-16 20:07 +0100
    Re: Fast String search algorithm Roedy Green <see_website@mindprod.com.invalid> - 2011-12-16 13:32 -0800
  Re: Fast String search algorithm Gene Wirchenko <genew@ocis.net> - 2011-12-16 12:12 -0800
    Re: Fast String search algorithm glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2011-12-16 21:22 +0000
  Re: Fast String search algorithm Arne Vajhøj <arne@vajhoej.dk> - 2011-12-16 22:20 -0500
    Re: Fast String search algorithm Lew <lewbloch@gmail.com> - 2011-12-16 21:39 -0800
  Re: Fast String search algorithm Wanja Gayk <brixomatic@yahoo.com> - 2011-12-17 16:15 +0100
  Re: Fast String search algorithm Travers Naran <tnaran@gmail.com> - 2011-12-18 09:17 -0800

csiph-web