DFA

DFA（确定性有限自动机）引擎由输入驱动。

原理

该算法扫描输入字符串一次，并记住正则表达式中可能匹配的所有可能路径。例如，当在模式中遇到交替时，创建两个新路径并独立尝试。当给定路径不匹配时，将从可能性集中删除它。

启示

匹配时间受输入字符串大小的限制。没有回溯，引擎可以同时找到多个匹配，甚至重叠匹配。

与 NFA 引擎类型相比，此方法的主要缺点是引擎可支持的减少的功能集。

例

将 a(b|c)a 与 abadaca 相匹配：

abadaca      a(b|c)a
^            ^        Attempt 1      ==> CONTINUE

abadaca      a(b|c)a
 ^           ^        Attempt 2      ==> FAIL
               ^      Attempt 1.1    ==> CONTINUE
                 ^    Attempt 1.2    ==> FAIL

abadaca      a(b|c)a
  ^          ^        Attempt 3      ==> CONTINUE
                   ^  Attempt 1.1    ==> MATCH

abadaca      a(b|c)a
   ^         ^        Attempt 4      ==> FAIL
               ^      Attempt 3.1    ==> FAIL
                 ^    Attempt 3.2    ==> FAIL

abadaca      a(b|c)a
    ^        ^        Attempt 5      ==> CONTINUE

abadaca      a(b|c)a
     ^       ^        Attempt 6      ==> FAIL
               ^      Attempt 5.1    ==> FAIL
                 ^    Attempt 5.2    ==> CONTINUE

abadaca      a(b|c)a
      ^      ^        Attempt 7      ==> CONTINUE
                   ^  Attempt 5.2    ==> MATCH

abadaca      a(b|c)a
       ^       ^      Attempt 7.1    ==> FAIL
                 ^    Attempt 7.2    ==> FAIL