我阅读了http://swtch.com/~rsc/regexp/regexp1.html,其中作者说,为了在正则表达式中进行反向引用,在匹配时需要回溯,这使得最坏情况的复杂度呈指数级增长.但我并不确切地知道为什么反向引用会引入回溯的必要性.有人可以解释为什么,也许提供一个例子(正则表达式和输入)？
regex complexity-theory computer-science backreference time-complexity
backreference ×1
complexity-theory ×1
computer-science ×1
regex ×1
time-complexity ×1