有关面试算法题的讲解视频请参看：
如何进入google,算法面试技能全面提升指南

有这么一道面试题，要求我们根据给定规则，构造一个字符串识别引擎，也就是实现一个正则表达式引擎，题目如下。

一个简单的正则表达式是由数字和字母组合而成的字符串，其中包含有称之为“元字符”的元素，例如”.”,字母数字组合，”*“，或者是两个简单正则表达式的连接 ，具体例子有： a,aW,aW.9,aw.9*,和aW.*9*,都是简单的正则表达式。对于正则表达式r,以及字符串s,他们相互匹配必须满足以下几个条件：
1 ： 如何r 是以数字，字母开头，并且r的第二个字符不是*,那么s要匹配r,则s必须以同样的数字或字母开头.

2：如果r 以数字或字母开始，后面跟着一个星号”*”,s要想匹配r的话，那么s必须能分解成两部分s1,s2,其中s1包含0个或多个r处于*号前那一部分数字或字母，而且s2与 r 的星号后面那部分要完全相同。

3： 如果r 以符号 “.” 开始，那么s要匹配r的话，s除去第一个字符后，剩下的部分要与r除去”.”之后的部分完全匹配。

4: 如果r以 “.”,“*” 开头，s要匹配r的话，s 必须可以分割成两部分s1,s1长度可以是0， 而s2必须与r除去开头两个字符后的部分完全匹配。

5: r还可以包含两个元字符， “^”和”$”,“^”表示开头匹配，”$” 表示末尾匹配，如果r以符号”^”开头，那么s要以r匹配的话，它必须分解成两部分，s1 和 s2,s1要能够与r完全匹配，同理，如果r以符号$j结尾，那么s2要能与r完全匹配。

举个具体例子，如果 r = aw9,s要匹配r,则只要s包含字符串”aw9”,如果r=^aw9,那么s必须以”aw9”开头才能和r匹配， 如果r=$aw9,那么s必须以”aw9”结尾才能和r匹配。r=a.9,那么s = aW9,xyaW9123 可以和r匹配，但如果s=aw89则不能匹配，r=a.*9 就可以和s=aw89匹配， r=aw*9 就可以和a9,aw9,aww9,aww…9匹配。

要求你实现一个算法，满足正则表达式匹配规则，给定正则表达式r,判断s是否能匹配r.

这道题无论是从算法设计还是代码实现上，难度都是相当大的，我有点怀疑在实际的算法面试中是否会真有人出这种题，但正则表达式的算法设计思想相当优美和巧妙，我觉得有必要仔细的研究和掌握,由于这个问题比较难，内容也比较多，我们需要分几节来处理。

正则表达式算法涉及到一个概念，叫非确定性有限状态自动机。前面我们提到过有限状态自动机，它的特点是从一个状态转换到另一个状态时，必须要有对应的输入，非确定性状态机的特点是，从一个状态转换到另一个状态时，不需要有确定的输入。

汤普森构造

最简单的正则表达式是只含有一个字符，如 r = a,这样的表达式我们可以对应下面的状态机：

如果字符串含有一个字符a,那么就从初始状态进入结束状态，如果s不包含字符a那么状态机就会一直处于初始状态，当s所有字符都扫描后，如果状态机不处于结束状态的话，那么s就不能和r匹配。

两个正则表达式前后连接也简单，下面的汤普森构造就表示两个表达式r1=a,r2 = b合在一起构成一个表达式 r = ab.

中间的ε表示不需要任何输入，就可以直接从第二个状态进入第三个状态。

两个正则表达式可以通过”或“操作联合在一起， 例如 r = a | b,那么对应的汤普森构造如下：

如果表达式含有星号，那表示匹配时可以把星号前面的部分重复0次或多次，例如 r = a*,这种汤普森构造如下：

起始和结束状态的中间部分，完全可以是任何一种复杂的正则表达式结构。

如果表达式含有元字符+,那表示把加号前面的部分重复至少一次以上，例如表达式r = a+,它的汤普森构造如下：

如果表达式中包含元字符 ?,那表明问号前面的部分可以重复0次或1次，对应的汤普森构造如下：

任何复杂的正则表达式都可以由以上几种构造组合而成，我们看一个例子r = (D*\.D | D \. D*)

表达式中的点由于前面有一个转移符 \,所以这里的点不再是元字符，而是代表其愿意，就表示字母”.”. D表示的是0-9数字集合，[0-9].

1： 先构造 r = D

2: 构造 r = D*

3: 构造 r = D* .

4: 构造 r = D* . D

5: 同理构造 r = D.D* 再做或运算，得到的完全状态机如下

通过分析给定正则表达式，利用汤普森构造设计好非确定性有限状态自动机后，接下来，就要根据状态机进行 ”ε闭包“运算，根据运算结果，以及输入的匹配字符串，我们就可以在状态机的基础上，运行相关算法，实现字符串的匹配，这些都将是后面章节的内容。