> On 13 Oct 2019, at 00:37, Richard Wordingham via Unicode > <unicode@unicode.org> wrote: > > On Sat, 12 Oct 2019 21:36:45 +0200 > Hans Åberg via Unicode <unicode@unicode.org> wrote: > >>> On 12 Oct 2019, at 14:17, Richard Wordingham via Unicode >>> <unicode@unicode.org> wrote: >>> >>> But remember that 'having longer first' is meaningless for a >>> non-deterministic finite automaton that does a single pass through >>> the string to be searched. >> >> It is possible to identify all submatches deterministically in linear >> time without backtracking — I a made an algorithm for that. > > That's impressive, as the number of possible submatches for a*(a*)a* is > quadratic in the string length.
That is probably after the possibilities in the matching graph have been expanded, which can even be exponential. As an analogy, think of a polynomial product, I compute the product, not the expansion.
