擅长:python、mysql、java
<p>在DFA上,这应该不到一毫秒:</p>
<pre><code>$ time python3 -c 'import re; re.match("a?"*25+"a"*25, "a"*25)'
real 0m7.273s
</code></pre>
<p>把25改成100,它一辈子都不会终止。在</p>
<p>以下是DFA(grep)的外观:</p>
^{pr2}$
<p>在<a href="http://swtch.com/~rsc/regexp/regexp1.html" rel="nofollow">http://swtch.com/~rsc/regexp/regexp1.html</a>上有一个关于这个主题的大讨论</p>