简单的模式匹配算法

指针StringPtr和PatternPtr分别指示主串String和模式串Pattern中当前正待比较的字符位置。

从主串String的第一个字符起，与模式串Pattern的第一个字符比较

• 若相等，则继续逐个比较后续字符
• 否则，从主串的下一个字符起，重新和模式的字符比较

以此类推，直至模式Pattern中的每个字符依次和主串String中的一个连续的字符序列相等，则

• 匹配成功，返回String中第一个相等字符的序号
• 否则匹配不成功，返回值为0

int Index(SString String, SString Pattern) {
    int StringPtr = 1, PatternPtr = 1;
    while (int StringPtr <= String.length && PatternPtr <= Pattern) {
        if (String.ch[StringPtr] == Pattern.ch[PatternPtr]) {
            ++StringPtr; ++PatternPtr;		// 继续比较后续字符
        }else {
            StringPtr = StringPtr - PatternPtr + 2;
            PatternPtr = 1;					// 指针回退
        }
    }
    if (PatternPtr > Pattern.length)
        return StringPtr - Pattern.length;
    else return 0;
}

效率分析

从第三趟的结果可知，主串中，第3、4、5和6个字符是a、b、c、a（与模式串已经匹配），由模式串自身可知：首字符a与b、c不同，而与尾字符a相同。所以第三趟失配后，主串指针回退到4的位置和模式串第一个字符a开始比较，以及接下来的两次比较也是重复的，模式串在不断地进行自我比较。

可以直接比较主串7，和模式串2位置的字符（即第六趟的第二步）。所以就诞生了下面这个：

主串指针不回退，且模式串回退位数仅与自身结构有关的算法

KMP算法

基本概念

前缀：除去最后一个字符后，字符串所有的以第一个字符开头的头部子串 后缀：除去第一个字符后，字符串所有的以最后一个字符结尾的尾部子串 部分匹配值：字符串的前缀和后缀的最长相等前后缀长度

原理

计算模式串的部分匹配值(Partial Match)的表

模式串p位置，与主串当前位置s的字符不匹配时， 子串（模式串）需要向后移动的位数 = 已匹配的字符数 - 对应的部分匹配值 即：Move = p - PM[p-1]​

以第二次匹配为例，主串的ｂ与模式串的ｃ不匹配， 已匹配的 'abca' 的前缀ａ和后缀ａ为最长公共元素，已知ａ与ｂ、ｃ均不同，与后缀ａ相同，故ａ与主串ｂ、ｃ无须再重复比较，直接将子串移动Move个位置，用子串前缀后面的元素与主串匹配失败的元素开始比较即可。

改进

next数组

p位置匹配失败，要查看PM[p-1]，不方便，于是将PM表右移一位，得到next数组

注意：

1. 若是第一个元素匹配失败，需要将模式串右移一位，所以第一个元素右移后的空缺用-1填充。
2. 最后一个元素溢出，但最后一个元素的部分匹配值时给下一个元素使用的，显然没有下一个元素，故可以舍去。

此时：Move = p-next[p]

程序表述

计算机编程实现前述的模式串右移Move个位置过程，表达为指针p回退到新的位置，即：p = p-Move = p-(p-next[p]) = next[p]

next[p]的含义：在子串的第p个字符与主串发成失配时，跳到子串的next[p]位置重新与主串当前位置进行比较

nextval数组