1、简单模式匹配算法
对一个串中某子串的定位操作称为串的模式匹配，其中待定位的子串称为模式串。算法的基本思想：从主串的第一个位置起和模式串的第一个字符开始比较，如果相等，则继续逐一比较后续字符；否则从主串的第二个字符开始，再重新用上一步的方法与模式串中的字符做比较，以此类推，直到比较完模式串中的所有字符。若匹配成功，则返回模式串在主串中的位置；若匹配不成功，则返回一个可区别于主串所有位置的标记，如“0”。
算法实现代码如下：
2、KMP算法
设主串为S1S2…Sn，模式串为p1p2…pm，在上一节的简单模式匹配算法过程中有一个多次出现的关键状态，见表4-2，其中i和j分别为主串和模式串中当前参与比较的两个字符的下标。
说明：上面1）~7）步骤介绍的求解next数组的方法虽然不是一种高效方法，但是在做选择题时是一种方便的手工求解方法。
讲过了如何手工求next数组的方法，下面介绍一种适用于转换成代码的高效的求next数组的方法。
3、KMP算法的改进
先看一种特殊情况，见表4-7。当j等于5，发生不匹配时，因next[5]=4，则需将j回溯到4进行比较；又因next[4]=3，则应将j回溯到3进行比较……由此可见，j需要依次在5、4、3、2、1的位置上进行比较，而模式串在1到5的位置上的字符完全相等，因此较为聪明的做法应该是在j等于5处发生不匹配时，直接跳过位置1到4的多余比较，这就是KMP算法改进的切入点。
