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