Re: Leftmost longest match with DFA search

Stefan Monnier <monnier@[EMAIL PROTECTED]
> writes:

[snip]
> >> The "obvious" solution of turning the problem "search for RE" into
the
> >> problem "match .*RE" (where I use "match" here to mean "anchored
> >> search") only gives you the leftmost shortest match.
> > [snip]
> >> Stefan
>
> > I've used the approach to compile a DFA for the reverse RE, say ER,
and
> > first match .*ER on the reverse text to find the leftmost anchor
point.
> >   Then match RE from that point to find the longest span.
>
> Interesting.  But doesn't it basically force you to scan the complete
text?
> That can be impractical.

You don't (always) need to scan the complete text.  You can perform
that reversed search on increasingly longer prefixes of the text.  If
you increase the lengths of the prefixes by a constant factor, you
work for a time in O(K) to find a leftmost match when the latter
completely lies in the first K characters.

Danny