我从中学到了本文关于ripgrep实现回溯的正则表达式引擎在某些情况下可能非常慢，但我不太明白为什么。有人可以简单地解释一下为什么以下 python 代码片段（在链接的文章中作为示例给出）非常慢吗？
>>> import re
>>> re.search('(a*)*c', 'a' * 30)
答案1
基本上，问题在于a模式中的双重重复。该部分a*允许任意数量的a，而周围的(·)* 还允许包含任意数量的模式。
这允许使用大量可能的方法来将模式与a' 字符串进行匹配。现在忽略，像( Five 's)b这样的字符串可以匹配为, , , , , ... 匹配字符串的方法有指数级的数量。aaaaaa(aaaaa)(aaaa)(a)(aaa)(aa)(aaa)(a)(a)(aa)(aaa)(aa)(aa)(a)
最后b，回溯引擎将尝试一种匹配 的方法a，意识到它找不到b，返回一步，尝试另一种方法，意识到它找不到b，...并采取一种方法花了很长时间来穷尽所有可能的安排，之后就失败了。
网上关于这个主题的文章比我写的要好得多。去读一下这些：
失控的正则表达式：灾难性的回溯Jan Goyvaerts 的作者描述了这个问题以及一些预防方法。
正则表达式匹配可以简单而快速（但是......）Russ Cox 也描述了这个问题，以及将正则表达式实现为有限自动机，而不使用回溯，因此不受此问题的影响。它还有图片。
在实践中，如果可以的话，请避免允许多种方式匹配字符串的模式。这里的例子，(a*)*c，显然是愚蠢的，因为它相当于a*c没有嵌套重复。