转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/70971767200953105952749/
对于字符串处理，常用的有这么几个工具，kmp，trie树，trie图，后缀树，后缀数组，正则表达式，DFA，NFA。下面就这些算法，数据结果及模型进行下简要的说明，并研究下它们之间的联系。
其中kmp，trie树，trie图联系紧密，trie图可以看成是kmp和trie树的结合，它是Aho等人改进了kmp算法，使它可以处理多个模式串，同时kmp可以看成只有一个树分支的trie图。后缀树，后缀数组都保存了与后缀相关的信息，通常作为一个预处理，为其他计算提供快速查询服务。正则表达式，DFA，NFA，则是三种等价的形式，其中正则表达式匹配时，通常转换为NFA，或者DFA然后利用状态图转换，实现匹配，这也是大部分正则匹配引擎的实现方式。其实kmp，tire都可以看成是一种状态图表示。
kmp与trie图
kmp的思想就是用直到目前的匹配结果，帮助进行下一次匹配，而不是重新再从patten的头开始匹配。关键在计算转换表即失效函数，这个计算过程与整个匹配过程也是类似的。
失效函数，是作为模式串的前缀，同时作为当前前缀串的后缀的最长长度，这个长度实际上也是为了防防止错过可能的匹配，所能够往前跳跃的最长距离。第i项的计算可以由第i-1项得到，如此往前循环下去。
计算失效函数的程序如下：
t = 0;
f(1) = 0;
for(int i = 2 ; i <= n ; i++){
while(t > 0 && patten[t+1] != patten[i]){
t = patten[t];
}
if(patten[t+1] == patten[i])
t++;
f[i] = t;
}
注意t从循环开始前到结束始终代表当前求的f[i]的前一个f[i-1]值，这点是不变性。
主程序如下：
t = 0;
for(int i = 1 ; i <= n ; i++){
while(t >0 && patten[t+1] != text[i]){
t = patten[t];
}
if(patten[t+1] == text[i]) t++;
if(t == s) return ok;
}
这里t代表了当前patten与text匹配的长度，不过t只是在循环的最后才是这个长度，或者t = 0可以看做是i=0时的结果。
trie图则是首先将多个模式串用trie树表示，然后利用类似kmp的方法，求出所有前缀的失效函数，这个失效函数与kmp中的求法完全相同，都是不断的利用其前缀的失效函数。利用这个结构，便可以把单串匹配扩展到多模式串匹配。不过注意树的节点有多个分支，这样要把当前字符与所有分支的比较才行。
后缀树与后缀数组
后缀树就是一个字符串的所有后缀形成的trie树。后缀数组则是所有后缀经过排序后的数组，数组保存了所有后缀的索引。对于后缀数组关键是建立这个数组，可以利用倍增法得到O(nlogn)的算法。
倍增法，类似RMQ中的sparse table方法，与kmp类似的思路，就是要充分利用直到目前为止的计算结果，以简化未来计算的复杂度。这里就是用k前缀的排序结果，来加速2k前缀的排序。
用一般的方法，对所有的后缀排序：如果用快速排序需要比较nlogn次，但每次比较需要n,所以总的复杂度是n*nlogn。但通过利用倍增，可以降为nlogn。
基本思路就是我们首先比较后缀的k前缀的大小，利用k前缀的结果计算2k前缀的结果。
k前缀是指某个字符串的前k个字符。以字符串abcd为例，我们需要排列abcd,bcd,cd,d，我们可以先比较它们的1前缀，a,b,c,d按照1前缀的大小排好序，然后比较2前缀ab,bc,cd,d…。最后求出n前缀的排序结果话，整个后缀的排序实际上就完成了。
很明显根据1前缀排序，复杂度可以为nlogn，然后通过k前缀计算2k前缀的排列，这一步我们可以通过nlogn的时间求出，原因是当我们得到了k前缀的排列，然后计算出它们的rank，这样我们就可以利用这个rank，在O(1)时间比较两个2k前缀的大小了。比如比较suffix[i]2k 与suffix[j]2k 可以通过把它们分成两段suffix[i]k suffix[i+k]k 与suffix[j]k suffix[j+k]k，这样就把一个2k前缀的比较，转化为2个k前缀的比较，k前缀可以由前面的计算直接得到。
可见我们每次处理一个k前缀，实际需要nlogn,因为倍增的关系，总共需要logn次，故总共复杂度为nlognlogn.如果排序使用O(n)复杂度的方法，最后就可以得到nlogn的算法了。
正则式 NFA DFA
正则表达式，是一种表现力很强的工具。通常用来进行文本处理。一个正则表达式可以很容易的转换为NFA，因为它们两个基本上是对应的。通常的一些正则匹配引擎都是把正则表达式转换为NFA或者DFA，然后利用NFA,DFA或者NFA/DFA来进行匹配的。
假设一个正则表达式长度为n，那么它可以在O(n)时间内转化为一个NFA，这个步骤需要利用到语法分析技术，同时很适合用递归解决。
NFA转换DFA
NFA又可以在有限时间内转换为DFA，通常使用的方法就是子集构造法，也就是我们首先从NFA的s0出发，求出那些通过E皮隆边可以到达的一个集合，然后根据输入字母表，对这个集合求出可以通过字母到达的新的状态集以及这个状态集可以通过E皮隆边到达的状态集组成的新集合，并对这些新集合逐步扩充直到无法扩充为止。
设NFA的原有状态格式为k,输入字母表个数为n。首先看这个扩充操作的复杂度，扩充首先要针对每个原集合中的状态进行，这样可能有k个需要扩充，每个状态的E皮隆闭包，实际上是通过这个状态进行DFS可以求得，这个复杂度可能达到k，所以如果求一个新的状态集合可能需要k*k次运算。下面还要看转化后的DFA可能存在的状态数目，如果与原来的NFA状态数差不多，那么这个NFA转化DFA的复杂度就是O(k^3)。需要注意的一点就是，特殊情况下转换后的DFA状态可能是指数集的(2^k),大概看一下，可以知道DFA的状态都是由NFA的所有状态的子集，而这个子集的数目极端情况可能达到2^k。实际中也存在这个极端情况，比如如下的正则表达式：
(a|b)*a(a|b)^(n-1)
比较
NFA，DFA都是通过模拟进行匹配的，可以看到与NFA相比DFA的每一步都是确定的，所以它的速度更快。所以一般来说DFA引擎效率更高些。但是由于存在上述情况，也就是DFA的状态数可能很大，以至于无法放入内存，这种情况下DFA的效率就会收到影响。如果一个模式，需要多次匹配，那么用DFA可能比较适合，因为NFA转换DFA，也需要开销，如果这个开销的坏处可以被匹配时的好处抵消，那么用DFA就比较合适，反之用NFA更好些。也就是因为NFA与DFA其实各有千秋，所以有的匹配引擎则使用了NFA/DFA混合的方式，来充分利用各自的优点。
模拟执行
通过上面，我们了解了正则表达式转换为NFA，NFA转换为DFA，我们还需要了解NFA,DFA的模拟执行的过程。对于NFA来说，可以这样做，这个过程实际上是并行的，用两个栈分别保存当前到达状态，和下一个状态，每次我们查看当前输入字符，然后通过当前状态+这个输入字符-》下一个状态，这个过程实际上叫做on-the-fly子集构造也就是实际上是上面NFA转换DFA的一个实时实现，通过当前状态+输入字符-》新状态集，新的状态集通过dfs E皮隆遍历，找到下一个状态集。
但是根据需求的不同，对于这个过程也需要不同的细节处理，比如如果我们只是判断某个字符串与当前NFA是否匹配，那我们只要一直执行下去，直到字符串结束，然后检查这个结束时的状态集是否包含终止状态就可以了。但是如果是在搜索，如果我们选择最短匹配的那个，这样按照上面的过程，只需要每次对状态集合判断一下是否存在终止状态即可。但是如果按照posix NFA，需要找最长匹配的话，就需要记录下匹配过程中出现的所有终止状态，当无法扩展状态时，返回去寻找最长的那个匹配。这个过程就需要保存中间状态。
当然上面这个是一个并行执行NFA的方法，当然还存在通过串行回溯来实现NFA的方法，也就是先从某一条路找下去，如果不行则返回从另一条路继续寻找匹配。<<精通正则表达式>>这本书的作者就是按照串行回溯实现来说的，这个方法就类似于走迷宫的过程。
如果把NFA单纯看成一个图的话，正则匹配，实际上就是给图中的边起个名字，看一下是否存在某条路径。这样并行模拟，就相当于BFS，而串行回溯则相当于DFS。可以看到它们模拟的复杂度是O(n*k),其中n是字符串长度，k则是模式串长度或者NFA的状态树。对于DFA的模拟方法，就简单了，因为每次都是确定的。所以整个过程只产生一条路径。
同时要注意，因为NFA很好的保存了原有正则式的结构，这样我们就可以很好的利用它来，计算子匹配表达式()。但是DFA就不行了，它已经背离正则式的本来面目，很难利用它追踪原来的子表达式，所以DFA引擎不支持这个运算。
关于正则表达式更详细的内容可以参考：编译原理龙书 静态正则表达式