Как обратные ссылки в регулярных выражениях требуют обратного отслеживания?

Я читал http://swtch.com/~rsc/regexp/regexp1.htmlи в нем автор говорит, что для того, чтобы иметь обратные ссылки в регулярных выражениях, нужен возврат при сопоставлении, и это делает сложность в худшем случае экспоненциальной. Но я не совсем понимаю, почему обратные ссылки вызывают необходимость поиска с возвратом. Может кто-нибудь объяснить, почему, и, возможно, привести пример (регулярное выражение и ввод)?

20
задан Andy Lester 19 June 2012 в 15:25
поделиться