Re: pattern finding problem

[Quantum Mechanic <quantum_mechanic_1964@yahoo.com>]

I don't think you can do that without (??:code)
blocks.

Have you looked at Regexp::Common? There are examples
there (such as for palindromes) that might be useful.

--- "Aaron J. Mackey" <amackey@pcbi.upenn.edu> wrote:
> 
> On Mar 2, 2004, at 9:37 AM, Jeff Abrahamson wrote:
> >
> > Do you allow overlapping patterns?  For example,
> if you are looking
> > for 1212, does the following string contain three
> instances or only
> > two?
> >
> >     12121212
> >
> 
> Yes, three.
> 
> > Do you allow intervening characters?  Searching
> for 12, do you match
> > on this?
> >
> >     132
> 
> If the pattern is "2 of [12] in a substring of
> length 3", then yes.  If 
> the pattern is "1 of '12' in a substring of length
> 3", then no.
> 
> > Are you doing full regex matching, subsequence
> matching, or simple
> > string matching?  If the latter, I guess this is
> easy using KMP and
> > can be done in linear time, so you must be asking
> about regex...
> 
> Regex matching, normally because the pattern of
> interest has ambiguity
> 
> > In the regex case you can simplify the problem by
> creating a new
> > alphabet with symbols P and Q.  Create a new
> string S on the new
> > alphabet, where the k-th symbol of S is P if an
> instance of your
> > pattern (of length less than B) begins at location
> k in the original
> > string.  Otherwise symbol k is Q.  With the symbol
> at position k store
> > the length of the shortest instance of the pattern
> that begins at
> > position k.
> 
> Could this handle overlapping cases?
> 
> -Aaron
> 


=====
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Quantum Mechanics: The dreams stuff is made of

__________________________________
Do you Yahoo!?
Yahoo! Search - Find what you?re looking for faster
http://search.yahoo.com
-
**Majordomo list services provided by PANIX <URL:http://www.panix.com>**
**To Unsubscribe, send "unsubscribe phl" to majordomo@lists.pm.org**