Aaron J. Mackey on 3 Mar 2004 16:48:16 -0000

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

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?


Yes, three.

Do you allow intervening characters?  Searching for 12, do you match
on this?


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?


**Majordomo list services provided by PANIX <URL:http://www.panix.com>**
**To Unsubscribe, send "unsubscribe phl" to majordomo@lists.pm.org**