我对使用正则表达式并不陌生，而且我理解它们所基于的基本理论——有限状态机。
我不太擅长算法分析，也不明白如何将正则表达式与基本的线性搜索进行比较。我之所以这么问，是因为表面上看这像是一个线性数组搜索。(如果正则表达式很简单)
我可以去哪里学习更多关于实现正则表达式引擎?
这是最流行的概要之一:正则表达式匹配可以简单而快速。针对字符串运行dfa编译的正则表达式确实是O(n)，但可能需要高达O(2^m)的构建时间/空间(其中m =正则表达式大小)。
您熟悉术语确定性/非确定性有限自动机吗?
真实的正则表达式(当我说真实的时，我指的是那些识别正则语言的正则表达式，而不是几乎所有编程语言都包含反向引用等的正则表达式)可以转换为DFA/NFA，两者都可以在编程语言中以机械的方式实现(NFA可以转换为DFA)
你要做的是:
- 找到一种方法将正则表达式转换为自动机
- 用您喜欢的编程语言实现对自动机的识别
这样，给定一个正则表达式，您可以将其转换为DFA并运行它以查看它是否匹配指定的文本。
这可以在O(n)中实现，因为DFA不向后(像图灵机)，所以它匹配字符串或不匹配字符串。这是假设你不会计算重叠匹配，否则你将不得不返回并重新开始匹配…
经典正则表达式可以以一种在实践中快速但具有真正糟糕的最坏情况行为(标准DFA)的方式实现，或者以一种保证合理的最坏情况行为的方式实现(将其保留为NFA)。标准DFA可以扩展为支持许多额外的匹配字符和标志，这利用了它基本上是回溯搜索的事实。
标准方法的例子随处可见(例如，内置于Perl中)。有一个例子，声称良好的最坏情况下的行为在http://code.google.com/p/re2/-事实上，它甚至比我预期的在最坏的情况下，所以他们可能发现了一个额外的技巧或两个。如果您对此感兴趣，或者关心编写程序来锁定给定病态输入的固体，请阅读http://swtch.com/~rsc/regexp/regexp1.html.