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