KMP算法：判断两个字符串的包含关系

一、知识储备

子串/子数组 ： 元素之间必须相邻且连续
子序列： 元素之间相对前后顺序不变，无须相邻，
两子串的包含问题：
str1是否包含str2 若包含，则从str1的哪个字符开始
str1 abc123def
str2 123def

kmp相关概念

前缀子串： 从字符串首位到该字符的前一位置（不包括该位置）
后缀子串 ： 从字符串第二位到该字符的前一位置
字符串中任意字符的匹配程度：该字符前缀子串与后缀子串相等的最大长度
字符串abcabcd
d的最长前缀子串为abcab
d的最长后缀子串为bcabc
next[] 表示每个位置的最长前缀和最长后缀的匹配程度
例子：

字符串	a	b	a	b	c	d
next数组	-1	0	0	1	2	3

二、暴力方法

遍历str1每个位置，以该位置为起始的子串与str2匹配，时间复杂度O(m*n) 其中m>=n

三、KMP加速匹配过程

3.1流程图

1. str1[i,X-1]与str2[0,Y-1]相等，str1[X]!=str2[Y]

2. 根据str2[Y]的next值，判断是否小于0
若小于0，说明Y是str2的首字符，与str1[X]不等，则j==X+1，str1从j位置与str2重新匹配
否则：找到str1中新的起始字符，记为j,此时判断str2[Z]==str1[X]
若相等，则继续X++,Z++，继续比较
若不等，则把Z当做Y，重复步骤2

例子

abcabct
abcabca

3.2kmp实质： 确定[i,j)位置上没有匹配str2的字符，可以通过反证法证明，实现了一次比较，跨越了str1上的k个字符

3.3求next数组

数学归纳法，有点类似DP
如下图，
步骤一：想求字符a的前缀后缀匹配最大值，只需知道其前一字符b的next值，
若next值<=0,则next[aIndex]=0
否则比较str2[x] == b
若相等，则next[aIndex] = next[bIndex]+1

若不相等，则把str2[c]当成步骤一中的b，重复这一过程,