正则表达式 NFA DFA
DFA自动机（Deterministic Final Automaton 确定有限状态自动机）和NFA自动机（Non deterministic Finite Automaton 非确定有限状态自动机）。
对比来看，构造DFA自动机的代价远大于NFA自动机，但DFA自动机的执行效率高于NFA自动机
假设一个字符串的长度是n，如果用DFA自动机作为正则表达式引擎，则匹配的时间复杂度为O(n)；如果用NFA自动机作为正则表达式引擎，由于NFA自动机在匹配过程中存在大量的分支和回溯，假设NFA的状态数为s，则该匹配算法的时间复杂度为O（ns）。
NFA自动机的优势是支持更多功能。例如，捕获group、环视、占有优先量词等高级功能。这些功能都是基于子表达式独立进行匹配，因此在编程语言里，使用的正则表达式库都是基于NFA实现的。
正则表达式
1.贪婪模式（Greedy） text=“abbc” regex=“ab{1,3}c”
2.懒惰模式（Reluctant） text=“abc” regex=“ab{1,3}?c”
懒惰模式的回溯是回溯正则表达式中一个匹配字符
3.独占模式（Possessive）
同贪婪模式一样，独占模式一样会最大限度地匹配更多内容；不同的是，在独占模式下，匹配失败就会结束匹配，不会发生回溯问题。
text=“abbc” regex=“ab{1,3}+c”
优化
- 使用独占模式
- 减少分之选择 用三次index代替“(X|Y|Z)”
- 减少捕获嵌套 非捕获组则是指参与匹配却不进行分组编号的捕获组，其表达式一般由（?:exp）组成
String text = "<input high=\"20\" weight=\"70\">test</input>"; String reg="(?:<input.?>)(.?)(?:</input>)";