字符串匹配(2)-普通模式匹配

    主要是关于CLRS的笔记。所谓模式匹配，很好理解，就是在Emacs中crtl+s,或者Word中ctrl+f,即查找一个输入子串的位置。如找gitt在sagittarix中的位置。五中方法可以解决：1) 蛮力/朴素(两词一个意思)；2) Rabin-Karp；3)有限自动机；4)Knuth-Morris-Pratt算法(KMP)；5) Boyer-More(BM)算法
1) 朴素，老老实实一步一步做
2) 将子串转化成k进制数，比较数或者(模)
3) 有限自动机这东西不熟，希望自己能在下面给出它的代码
4) KMP的主要思想是用前缀函数来做，即用前缀函数记下某一模式前缀在模式中出现的下一位置，这样可以减少比较次数。
5) BM据说与KMP很像，但是不太清楚，有空时看看。
2)~5)之所以比1)快，是因为用到了预处理，以及充分削减了1)中的重复比较。下面给出有限自动机和KMP的代码。
有限自动机实现代码：
KMP实现代码：