看得见的算法

正则表达式通常被视为一个“黑盒”：你输入规则和文本，它告诉你是否匹配。但内部发生了什么？为什么有时候它会慢得要死？

为了直观地理解 NFA (非确定性有限自动机) 的并行（或回溯）特性，我编写了一个简单的交互式演示。

交互演示

演示说明

1. 编译：点击“编译并重置”，JS 脚本会将正则表达式转换为 NFA 图。
2. 初始状态：NFA 从起始节点开始，自动通过所有的 $\epsilon$ (Split) 边，计算出初始的状态集合。
3. 步进 (Step)：每点击一次“下一步”，引擎读入一个字符。
   • 引擎检查当前集合中所有的状态。
   • 如果某个状态能接受这个字符，就转移到下一个状态。
   • 新的状态再次通过 $\epsilon$ 边扩散。
   • 形成新的状态集合。
4. 并行特性：你会注意到，在某些时刻（比如匹配 (b|c)* 时），状态集合里可能同时有多个状态。这就好比量子力学中的“叠加态”，NFA 同时在尝试多条路径。

这就是为什么 NFA 引擎（如 RE2）能保证线性时间复杂度的原因：它不需要回溯，它只是维护了一个有限的状态集合。