Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.java.programmer > #10812
| From | glen herrmannsfeldt <gah@ugcs.caltech.edu> |
|---|---|
| Newsgroups | comp.lang.java.programmer |
| Subject | Re: Fast String search algorithm |
| Date | 2011-12-16 21:22 +0000 |
| Organization | Aioe.org NNTP Server |
| Message-ID | <jcgcqr$17p$1@speranza.aioe.org> (permalink) |
| References | <i02ne7ptvvl8ofv9uracdu2jm3oq61v2h3@4ax.com> <eg9ne7d8tt9vf7brjrpo7d5cgrf0p10bnu@4ax.com> |
Gene Wirchenko <genew@ocis.net> wrote: > On Fri, 16 Dec 2011 10:08:02 -0800, Roedy Green > <see_website@mindprod.com.invalid> wrote: >>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? > Look up the Boyer-Moore string search algorithm. Well, Boyer-Moore still scans linearly, but just does it faster. Still, you could use something Boyer-Moore related if you know which characters were in each record. If a record didn't have a character in your substring, then it couldn't have the substring. Still, understand Boyer-Moore before you get much farther with string searching. -- glen
Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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