字符串匹配问题："字符串A是否为字符串B的子串?如果是的话出现在B的哪些位置?"

字符串A称为模式串，字符串B称为主串（模式）。

Brute-Force算法：
假设n为主串长度，m为模式串长度。每一轮字符串比较：最差的情况为模式串最后一个字与主串不同其他都相同（如模式串为AAB，主串对应部分为AAC），必须走完整个字符串才能得出结果，因此复杂度为O(m)。所有轮字符串比较：最差的情况是移动到最后一次比较才寻找得到，总共需要n-m+1次，主串通常比模式串长很多，故Brute-Force时间复杂度为O(nm)。
暴力匹配中，每一趟失败都是从模式后移一位再从头开始匹配，此尽可能减少比较的趟数是算法优化的方向，也是KMP算法的核心思想：每次匹配过程中推断出后续完全不可能匹配成功的匹配过程，从而减少比较的趟数。
###利用模式串存在的规律，对BF的优化

思路一

通过求字符串的前缀和后缀与部分匹配值求模式串的next数组

• 前缀：除最后一个字符外，字符串的所有头部子串
• 后缀：除第一个字符外，字符串的所有尾部子串
• 部分匹配值(Partial Match,PM)：字符串的前缀和后缀的最长相等前后缀长度

移动位数 = 已匹配的字符数-对应的部分匹配值（最后一个匹配字符的对应部分匹配值）
More = (j -1) - PM[j-1]，j为移动指针

原理：减少匹配趟数需要排除不可能匹配成功的过程。每一趟模式匹配中，都是将模式串与主串比较，模式串为关键，每一次匹配都是对模式串每个字符的比较，匹配失败为有一个字符不同，但可能有部分匹配成功，若模式串存在特殊规律，在部分匹配成功的字符串中可能存在与模式串前缀相同的后缀字符串，或与前缀不同的部分即完全不可能匹配的后缀字符串，移动即不进行匹配与前缀不同的字符，不需要对主串进行逐一后移比较，可减少匹配趟数在已匹配的字符串中找到从最后开始的出现的最长相等前后缀的字符子串，从该字符串开始，移动的位数就是已匹配的字符数-该字符子串的长度（即PM值）

next数组为PM表右移一位：

• 第一个元素右移后用-1表示，因为若是第一个元素就匹配失败，则需将子串向右移一位，不需要计算计算子串移动的位数
• 最后一个元素在右移过程中溢出，部分匹配值为在已匹配的字符使用，若最后一个元素匹配，则模式匹配完成，故可以舍去

思路二

利用状态机的思考KMP