Re: [Haskell-cafe] major speed improvement: regex-tdfa reaches 1.0.0

ChrisK wrote:

The previous versions allowed bad combinations of pattern and searched text length to scale badly in the length of the text. Previously the worst case for text of length N was O(N^3).

The new worst case asymptotic runtime scaled as O(N). There is never any backtracking. And the worst case storage space is independent of N.

That's an awesome result. :-) Thanks! Martijn.