KMP
学了老久KMP惹，至今为止还没有写过一篇博客来复习复习，那么今天它就来惹(小声BB:其实是没有心情刷题)
初学者肯定会问:学KMP有什么用a?我打我的暴力它不香嘛?然而，不友好的数据会用TLE给予你以重拳一击
KMP匹配算法模拟
好了，废话不多说，KMP主要是用于字符串的匹配问题，比如，现在给你两个字符串S和T，让你求T在S中出现过多少次，分别是在哪儿?
S
:
a
b
a
b
a
b
a
b
c
a
S:ababababca
S:ababababca
T
:
a
b
a
b
a
b
c
a
T:abababca
T:abababca
设当前匹配到的S和T中的下标分别为i和j
如下图，当匹配到(a)图情况时，发现S[ i ]!=T[ j ],失配了，如果用暴力算法，就会让 j = 1 , i = i − j + 1 j=1,i=i-j+1 j=1,i=i−j+1
然而，可以很明显的看到，在这一次的匹配中，我们知道了S中
i
−
j
i-j
i−j到
i
−
1
i-1
i−1的字符是与T中前
j
j
j个字符是相同的，那么如果我们可以知道若T中前j个字符可以匹配时，跳到位置
k
k
k可以让这前
j
j
j个字符中的前
k
k
k个字符和后
k
k
k个字符为最长前缀后缀，那么就可以不改变
i
i
i直接将
j
j
j跳到该位置上，如图(b),已知T中前
6
6
6个字符是匹配成功的，那么将
j
j
j跳到第
4
4
4个位置，此时T中前4个字符与S中的以
i
−
1
i-1
i−1为结尾的4个字符就相等惹a这其中的妙处就让
走进米奇妙妙屋后吃了妙脆角的妙蛙种子大佬们来妙啊～～～讲解叭，反正让我画图是不可能的，这辈子都不可能的
求解next数组
n e x t [ i ] next[i] next[i]表示模式串中前 i i i个字符的最长前后缀长度，