一 定义
1 主串S = S₁S₂…Sn, 即由n个字符组成的字符串
2 模式串T=T₁T₂ …Tm,即由m个字符组成的字符串
3 字符串匹配问题定义:给定主串S与模式串T,若S中含有T,返回T第一次出现的位置,否则返回-1.
二 普通做法
for(int i = 0; i < n; i++) {
for(int j = 0; j < m && s[i + j]==t[j]; j++); if(j == m) return i;
}
return -1;
三 有限状态自动机
有限状态自动机FSA可以用5元式定义，即：<输入字符集，状态集，初始状态集，接受状态集，状态转移函数>。我们常用的正则表达式其实就是FSA，能够用有限状态自动机表示的语言即为正则语言.
字符串匹配本质也是一个模拟有限状态自动机的过程，即构造一个FSA，只接受所有含有字符串T的字符串。若输入串S被该FSA接受,则表明S含有T.
假设T=”ababcab”
其上述普通做法所模拟的FA可以描述如下:
每次内层循环开始，状态为0，若下一个字符串为a，则状态转为1，也即j++，直到j=7，即识别了字符串”ababcab”，到达了接受状态7。 相反，假设在状态2时，下一个输入字符不是’a’，则匹配失败，此时应该重新回归起始状态，在代码中的具体体现就是退出内层循环，i++，再进入内层循环，此时j=0，即重新从状态0开始。
但是上述FSA不是通常意义上的FSA，其效率非常低，有两个原因：
1） 每次匹配失败，状态重新回归0，即j=0。
2） 每次匹配失败，回退1…j个字符，即i=i+1，本来已经读取到了i+j。
上述两个回退分别体现在内循环与外循环，，比如我们在j=2时发现匹配失败，此时已经读取了i+2个字符，但是退出内层循环，只是i++，再重复读取字符，即从i+1开始重复读取字符，而第i+1，i+2个字符已经被读取了，按道理不应该重复计算。并且状态2应该具有对历史匹配的记忆能力，即状态2表示了0->1->2的过程，表示“ab”已经匹配了。
如何利用这些已知匹配信息来提高计算速度呢？主要从两点入手：
1）…
