Re: (Unsure where to post)

From: Colin Percival (cperciva_at_sfu.ca)
Date: 12/10/04 

Date: Thu, 9 Dec 2004 23:11:34 +0000 (UTC)

atomx <prothe113@yahoo.com> wrote:
> What is an efficient algorithm for searching a large string (a block of
> memory that's 10-20mb in size) for a varying number of strings, each of
> which is of varying length and may contain zero or more "don't-care"
> characters at any position? The alphabet is large (256 -- searching
> for bytes) and the contents of the pattern and the search text are both
> fairly evenly distributed across the alphabet. The "don't-care"
> characters are fixed-length -- each one will match one and only one
> symbol. Patterns are long-ish (between 30 and 150 bytes each).

How many don't-care symbols do you have in a typical pattern? If
it's small, start with a filtering stage which takes the longest
don't-care-free substring of each pattern and searches for those
within the text.

Colin Percival

Relevant Pages

  • Re: what is the quickest way to find out whether a string contains another string?
    ... Why would anyone want to use regular expressions to look for a plain ... Regular expressions are a tool for deciding whether a String or ... searching is a trivial degeneration of the problem addressed by regular ... input string into a pattern that matches only itself is the first task. ...
    (comp.lang.java.programmer)
  • Re: Regular expression for numeric
    ... That's a literal string. ... pattern you're searching for? ... -It search the pattern "t" in the ... strstris a standard function, ...
    (comp.lang.c)
  • heeeeeeeeeeeelp with awk/sed script
    ... hi gurus its me again.. ... I have a file and I need to put a comment on the string it found and insert ... a new line below that string/pattern I am searching. ... put a comment on the pattern and insert a new line ...
    (SunManagers)
  • what "google" do to search a pattern
    ... When i look for efficient ways of searching a string, ... what does google do for searching a pattern. ...
    (comp.lang.c)
  • Re: Sed pattern macth
    ... The pattern before and after these string are varying. ... My purpose ...
    (comp.unix.shell)