正则表达式存在最大长度吗？匹配过长的字符串会不会爆炸？

[LeeReamond]

如题，比如用|分隔了 2000 种情况。。

[justnull]

正则表达式实现一般是编译到状态机，所以

[justnull]

所以如果状态机遇到死循环是有可能超时的

[justnull]

至于状态太多，那得看具体实现，如果说|分隔 2000 种情况我觉得不会出问题

[justnull]

自动机的类型可以分为 DFA 和 NFA ，一般来说正则表达式引擎会选择 NFA ，因为 DFA 会存在状态爆炸的问题；但是 NFA 如果错误使用正则表达式，有可能因为回溯导致 CPU 满载
如：blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/

[justnull]

此外，使用 NFA 而不是 DFA 还有一个重要原因是为了支持更多的特性

[justnull]

TLDR：是的，滥用正则表达式可以造成机器瘫痪，如灾难性回溯(Catastrophic Backtracking)导致耗尽 CPU 资源，要触发这种陷阱只需很短的输入即可，不需要构造很长的表达式和输入

[dingwen07]

正则只要编译成确定有限状态自动机（ DFA ）之后，匹配字符串就只需要线性时间。
至于 regex 如何转换成 DFA ，常见的算法是先转 NFA 然后再转 DFA ，似乎需要指数时间。

[justnull]

如果正确使用正则表达式，理想情况下编译好的正则表达式的匹配时间与输入字符串长度成正比

[lithiumii]

cloudflare 就被自己的一条正则打趴下过

https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/

那条正则是

(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))

[efaun]

@justnull #6 好家伙, 你这是给楼主送铜币啊

[justnull]

@efaun 送铜币是什么？不太懂这个

[justnull]

@efaun 发这么多条是因为手滑不小心点了回复

[justnull]

@efaun 好吧，理解了这个系统。注册账户只是顺手回复一些力所能及的问题而已，没有关注过本站机制

[LeeReamond]

@justnull 感谢答疑