bug#16966: [PATCH] grep: optimization with the superset of DFA

[Paolo Bonzini]

Il 02/04/2014 00:21, Norihiro Tanaka ha scritto:

1 accccccccccccccccccccccccccccccccccccccc
2 cccccccccccccccccccccccccccccccccccccccc
3 cccccccccccccccccccccccccccccccccccccccc
4 cccccccccccccccccccccccccccccccccccccccc
5 accccccccccccccccccccccccccccccccccccccb

Then all lines are matched fast.  However, because matches multiple
lines, retry from the last line (line 5).  It's accepted by the
superset.  However, It's rejected by normal DFA.

On the other hands, It can be constituted just three DFA states.  It's
too simple.

             /\
            /  \
            \  /
             \/
  1:a ---> 2:CSET ---> 3:b

Does anything change if there are a few million c's?

Paolo