I was about to start a thread about a very similar problem; hope I'm
not hijacking this thread. However I am interested in a solution that
(1) scales to a potentially large number of alternate strings
(hundreds or thousands), which will hit, sooner or later, some max
limit in the builtin regexps and (2) is not limited to strings but can
be used for arbitrary objects. Therefore I am looking for a different
approach, perhaps a specialization of the general regexp search
More formally, given (a) an input sequence I and (b) a set of
'censored' sequences S, find and remove all the sequences in S that
appear in I. For instance, if
S = set([(a,), (a,b), (a,c), (c,), (d,a)])
I = (x, a, b, c, y, d, a, b), the filtered sequence would be:
O = (x, y, b)
i.e. the censored subsequences are (a,b), (c,), and (d,a).
As with regexps, if sequence `x` is a prefix of `y`, the longer
sequence `y` wins when both match (e.g. if (a,b) matches, it
For extra bonus, the algorithm should remove overlapping subsequences
too, i.e. for the input I above, the output would be (x, y) since both
(d,a) and (a,b) would match for (d,a,b).
With respect to complexity, I am mainly interested in len(S); len(I)
is small for my application, typically no more than 10. Of course, an
algorithm that scales decently in both len(S) and len(I) would be even
better. Any ideas or relevant links ?
PS: This is not a homework ;)