Bad performance of simple regular expression - why??
Manfred Nowak
svv1999 at hotmail.com
Tue Feb 6 04:14:56 PST 2007
Walter Bright <newshound at digitalmars.com> wrote
> If it fails, then fallback to the original method.
It is a ridiculous business to incorporate additional algorithms
because a current implementation is broken.
The well known chain of converting RE->NFA->DFA->minimal DFA
should handle that problem fast, because the minimal DFA for a RE of
the form ((a?)^n a^n) for fixed n is a chain of 2n+1 nodes, which
corresponds to the longest acceptable input plus final state.
In this chain the first n nodes are nonfinal, all others are final.
The first node is the start node.
All nodes have transitions to the next node under "a".
That is recognision time is linear in the length of the input: no
exponential behaviour.
-manfred
More information about the Digitalmars-d
mailing list