字符串匹配算法

有限状态机

一个有限状态机包含3部分：

1. 有限的状态集合，其中包含初始状态、中间状态和接受状态（或者叫做终止状态）
2. 有限的输入字母表
3. 状态转移函数

一个简单的两状态自动机如下：
状态集合为{0，1} 其中0是初始状态，也是中间状态，1是接受状态
输入表为{a，b}
状态转移函数表示为状态转移表如下：

状态	输入a	输入b
0	1	0
1	0	0

等价的状态转移图为：

此状态机可以接受最后具有奇数个a的字符的字符串，比如a，abaaa，而aa、abbaa等不会接受。

考虑匹配模式P=ababaca，对此可以建立的状态机如下：
状态集合{0，1，2，3，4，5，6，7} 其中0是初始状态，7是接受状态，其他的为中间状态。这里状态采用数字表示，且接受状态恰好为模式的长度，实际上状态也可用其他形式表示。
输入集合{a，b，c}
状态转移函数用等价的状态转移表表示：

状态	输入a	输入b	输入c
0	$\color{#FF3030}{1}$1	0	0
1	1	$\color{#FF3030}{2}$2	0
2	$\color{#FF3030}{3}$3	0	0
3	1	$\color{#FF3030}{4}$4	0
4	$\color{#FF3030}{5}$5	0	0
5	1	4	$\color{#FF3030}{6}$6
6	$\color{#FF3030}{7}$7	0	0
7	1	2	0

红色数字表示一个正确的匹配，即从初始状态0开始，依次读入a b a b a c a。
以状态5为例，下面解释分别读入a b c后要转入的下个状态。
状态5说明已经匹配了ababa，读入c，则变为ababac，转状态6；
读入a，

前缀
ababaa	不是P的前缀
babaa	不是P的前缀
abaa	不是P的前缀
baa	不是P的前缀
aa	不是P的前缀
a	是P的前缀

因此读入a，状态转1.
读入b，

前缀
ababab	不是P的前缀
babab	不是P的前缀
abab	是P的前缀

因此读入b，状态转4.
所以当读入新的输入时，要转移的状态为匹配P的最长前缀表示的状态。

因此采用有限状态机匹配字符串的流程为：

1. 根据模式构建有限状态机，即初始化状态转移表
2. 依次读入每个字符，根据状态转移表决定下个状态，当状态为接受状态时，表示找到一个合适的匹配。

代码工作主要为初始化状态机，非常适合P固定，而要匹配的字符串N较大的情况，此时时间复杂度为O(N)，P较短且输入集合较小时可以忽略创建自动机的损耗。