Re: pattern finding problem

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