alt Hacker NewsEven Thompson didn't use the linear time algorithm that's named after him in Ed and Grep. The Python and Perl implementations were inspired by Henry Spencer's regex, which was in turn reimplementing Thompson's backtracking implementations.
Even Thompson didn't use the linear time algorithm that's named after him in Ed and Grep. The Python and Perl implementations were inspired by Henry Spencer's regex, which was in turn reimplementing Thompson's backtracking implementations.
Are you sure it was Thompson who added backtracking to grep? Note also that the POSIX standard intentionally omits backtracking regex. It is a shame that others have not deprecated them.