Leftmost longest match with DFA search

Stefan Monnier wrote:
Can someone point me to articles that discuss various ways to get the
leftmost longest match when implementing regexp search using a DFA?
>
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.
--
Daniel Villeneuve
Kronos

>Can someone point me to articles that discuss various ways to get the
>leftmost longest match when implementing regexp search using a DFA?
>>
>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.


Stefan