正则表达式搜索的原理:
首先是解析正则表达式,把它表示成容易实现的等价树形形式。
然后是由模式串建立一个非确定的有限自动机(NFA)。NFA本质上是一个状态机,当读入文本字符时,活动状态被改变。状态机的当前状态为一个终止状态时,表示识别出一个字符串。
NFA构建完成之后即可直接进行搜索(即NFA-Thompson算法),速度很慢,原因是可能同时存在多个活动状态。
所以一般把NFA转换为DFA(确定有限自动机),它在任何时刻都只有一个活动状态,所以特别适合文本搜索。
但因为转换后的DFA的大小可能是原来的NFA的指数级,所以只有在模式串较短的时候才适用。
所以对于较大的模式串,通常用多个较小的DFA构造一个大的NFA,这种DFA和NFA结合的方法有较好的效率,就是DFA modules算法。
除此之外,正则表达式搜索还有其它算法,各有适用范围,有些位并行之类的较新的算法会有效率上的大提高。
了解了这些原理,实现你所说的那些图示就不是很难的事啦~~