In this very well written article, Russ Cox explains why most current regular expression implementations have exponential running times for certain patterns, while Ken Thompson’s NFA implementation from the 1960s is linear for all inputs. Cox suggests that the NFA approach is compatible with modern regex features and that this is how regular expressions should … Continue reading Regular Expression Performance