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
