正则表达式
正则表达式语法
一般的正则表达式语法：
- x，x是一个简单字符，匹配一个同样的字符
- xy，其中x和y都是正则表达式，匹配一段文本ab，其中x与a匹配，y与b匹配。
- x|y，其中x和y都是正则表达式，匹配文本a，其中x与a匹配或y与a匹配。
- x?，x+，x∗，分别表示匹配正则表达式x最多一次，至少一次，任意次。
我们可以通过圆括号来修改结合的优先级。
自动机
我们可以将正则表达式转换为自动机，比如a(bb)+a如下：
其中开始状态有一个单独的箭头指向，在图中为s0。而匹配状态的一个双圆包含，图中为s4。
上面图中展示的自动机为确定有穷自动机（deterministic finite automaton, DFA），因为每个顶点每个字符最多一条出边。当然的对应也有一种非确定有穷自动机（not deterministic finite automaton, NFA），如果某个顶点对于某类字符有多条出边，比如对于a(bb)+a，下图就是一个NFA。
我们可以添加一些不带标号的边，这样NFA看起来会更加简单易懂。
其中一条有向边上每个字符，表示即使没有输入新的字符，也可以从状态s3转移到状态s1。
正则表达式和NFA之间在功能上存在等价关系，每个NFA在功能上对应一个正则表达式，反之亦然。（同样，每个正则表达式在功能上都对应一个DFA，反之亦然）
从正则表达式构建NFA的方法首次由Thompson在他的1968年的CACM论文中提出。具体方法是通过将部分正则表达式转换为DFA的子图，之后合并这些子图得到完整的NFA。每个子图有开始顶点，但是没有匹配顶点，取而代之的是一个或多个悬置（dangling）边，这些边没有入点。
匹配单个字符的子图：
子图e1e2
子图e1|e2。
子图e?
子图e∗
子图e+
可以发现我们为每个正则表达式中的字符都创建正好一个顶点（除了括号），同时常数条出边。
我们可以通过之前讨论的方法移除所有没有标号的边，但是带有标号的NFA更加容易理解。
对于NFA，一般其匹配文本的算法是回溯，这在最坏情况下，时间复杂度是O(2m)，m是文本的长度。大部分语言中（比如java）的正则表达式的实现方式都是回溯法，因为它支持更加复杂的语法。我们可以用形如(a?)nan的模式，以及使用an文本（其中指数表示的是前面内容重复n次），可以将时间复杂度劣化到O(2n)。
考虑到DFA拥有线性的匹配性能，我们可以尝试将NFA转换为DFA来优化匹配性能，但是这对应的会花上更多的预处理时间和空间复杂度。下面我们讨论NFA转DFA的算法。设V为NFA中的顶点集合，E为其边集，其大小为n。我们对于任意X⊆V，都在DFA图中建立一个顶点vX，对于任意字符c，记Y为X中顶点经过一条标号为c的边以及任意个没有标号的边所能达到的顶点集合，则我们在DFA中加入一条边(vX,vY)，边的标号为c。
上面的算法可以构建一个DFA，但是预处理的空间复杂度和时间复杂度是O(2n)。我们可以采用另外一种折中的方案，就是惰性计算DFA。可以发现大部分DFA状态都是不可能抵达的，因此我们可以在匹配的时候惰性计算新的DFA状态。这样可以有效减少时间消耗，且仅匹配所花费的时间实际上是非常少的。但是空间复杂度的问题还没解决，一个简单的方案就是使用一个带淘汰算法的数据结构来存储DFA（比如LRU、LFU算法），这样可以保证内存不会溢出。
下面讲一些将时间复杂度优化到O(nm)的方式。一种就是用回溯+记忆化，但是缺点就是使用递归，可能爆栈，并且空间时间复杂度为O(nm)。一种更加好的方式是在处理每个字符的时候标记之前整个序列可以抵达的状态集合，并从这些状态衍生出新的状态。如果希望某个字符串中提取最多的匹配正则表达式的不相交的子串，则可以在每次遇到匹配就结束，并在处理新字符的时候将开始状态加入到状态集合中。