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

[Norihiro Tanaka]

Norihiro Tanaka wrote:
> s0: The position set is none. 
> s1: The position set is 1:a 
> s2: The position set is 1:a 2:CSET
> s3: The position set is 1:a 2:CSET 3:b (accepted)

Sorry, it was wrong.  It should be as follows.

s0: The position set is none.
s1: The position set is 1:a
s2: The position set is 1:a 2:CSET
s3: The position set is 2:CSET 3:b (accepted)
s4: The position set is 2:CSET

        1  accccccccccccccccccccccccccccccccccccccc
           ^ s1

        1  accccccccccccccccccccccccccccccccccccccc
            ^ s4

        1  accccccccccccccccccccccccccccccccccccccc
             ^ s4

              ......

1,000,000  cccccccccccccccccccccccccccccccccccccccb
                                                 ^ s4

1,000,000  cccccccccccccccccccccccccccccccccccccccb
                                                  ^ s3 accepted

Then re-searched with the superset because matched on multi-lines.

1,000,000  cccccccccccccccccccccacccccccccccccccccb
           ^ s0


1,000,000  cccccccccccccccccccccacccccccccccccccccb
                                ^ s1

1,000,000  cccccccccccccccccccccacccccccccccccccccb
                                 ^ s4

1,000,000  cccccccccccccccccccccacccccccccccccccccb
                                                 ^ s4

1,000,000  cccccccccccccccccccccacccccccccccccccccb
                                                  ^ s3 accepted


s0: The position set is none. 
s1: The position set is 1:a 
s2: The position set is 1:a 2:ANYCHAR
s3: The position set is 2:ANYCHAR 3:b (accepted)
s4: The position set is 2:ANYCHAR

1,000,000  cccccccccccccccccccccacccccccccccccccccb
                                ^ s1

1,000,000  cccccccccccccccccccccacccccccccccccccccb
                                 ^ s4

1,000,000  cccccccccccccccccccccacccccccccccccccccb
                                  ^ s0 rejected