Thompson 算法 · regex engine internals
写 a(b|c)*d 能匹配 "abcbcd"，看起来像魔法。其实它被编译成了一台状态机，匹配就是在这台机器上走。
NFA（非确定）：一个状态遇到一个字符可能跳到多个状态，要同时维护"当前可能在哪几个状态"。好建、好理解，但匹配时要跟踪状态集合。
DFA（确定）：一个状态遇到一个字符只跳到一个状态，匹配就是顺着一个指针走。快，但状态数可能爆炸（指数膨胀）。工程上常直接用 NFA（够用），或对常用正则预编译成 DFA（求快）。
输入正则和字符串（或点示例），点"匹配"，看结果和匹配过程。
你大概遇到过：一个正则跑着跑着卡死了。原因是回溯。
很多正则引擎用"回溯"实现 NFA：遇到分支先试一条路，走不通退回来试另一条。大多数情况没问题，但遇到 (a+)+b 这种嵌套量词 + 不匹配的字符串，回溯路径数指数爆炸——O(2ⁿ)。
解法是用 Thompson NFA（不回溯，同时跟踪所有可能状态）或预编译成 DFA——它们是 O(nm) 的，不会指数爆炸。这就是为什么 Rust 的 regex 引擎不会"灾难性回溯"——它用 Thompson 算法，而很多老引擎（PCRE、Python re）用回溯。选引擎要看它是不是回溯型，对用户输入的正则尤其要小心。