Paul, thanks for a lot of reviews and commits. However, it may be wrong. I ran several tests for the worst case.
$ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 >../k $ env LANG=C time -p src/grep -i kjjjjjjjjjjjjjjjjjjj ../k My version: real 0.74 user 0.43 sys 0.30 Simplified version: real 2.06 user 1.74 sys 0.31 It's slower than DFA. $ env LANG=C time -p src/grep -i 'a\|kjjjjjjjjjjjjjjjjjjj' ../k real 1.26 user 0.96 sys 0.30 I ran the test on Solaris 10 (SPARC) and HP-UX 11v2 (Itanium) - On HP-UX 11v2 $ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 >../k $ env LANG=C time -p src/grep -i kjjjjjjjjjjjjjjjjjjj ../k My version: real 2.9 user 2.6 sys 0.2 Simplified version: real 7.5 user 7.3 sys 0.2 Using DFA: $ env LANG=C time -p src/grep -i 'a\|kjjjjjjjjjjjjjjjjjjj' ../k real 3.2 user 3.0 sys 0.2 - On Solaris 10 $ env LANG=C time -p src/grep -i kjjjjjjjjjjjjjjjjjjj ../k My version: real 7.61 user 6.89 sys 0.71 Simplified version: real 24.44 user 23.71 sys 0.72 Using DFA: $ env LANG=C time -p src/grep -i 'a\|kjjjjjjjjjjjjjjjjjjj' ../k real 8.03 user 7.31 sys 0.71 Norihiro
