KMP算法（严蔚敏数据结构第二版）

KMP算法之前看过一次，看了好久才看明白，今天又学的时候发现啥也不会了，又看了好久，在这里整理一下思路，方便以后复习。

算法介绍

在我们常规的模式匹配算法中，每当匹配失败时，模式串都从第一个字符开始重新比较，KMP算法的改进在于：当匹配中出现字符不相等时，主串指针不回溯，模式串指针根据部分匹配的结果，尽可能的向右“滑动”一段距离，从而减少匹配次数。 kmp算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。 算法匹配过程如下： 这里可以看到第三次匹配时，模式串没有从头开始，而是直接比较了b，这是KMP算法的难点之一，即当匹配过程中产生失配时，主串中的第i个字符应该与模式中哪个字符比较呢？

这里我们以模式串s="abaab"为例，假设在比较s[3]处失配了，那么这时再比较可以从s[1]处开始，因为我们知道s[0]~s[2]匹配成功，即s[2]对应的主串位置应为’a’，s[0]=s[2]所以s[0]不需要再次匹配直接放到之前s[2]所在的位置即可，不难发现，这里移动的位置应该与模式串的前缀字符串和后缀字符串有关，这就是下面要讲的next数组。

next数组

next[j]=k：表示当模式中的第j个字符与主串中相应字符失配时，在模式串中需重新和主串中该字符进行比较的字符位置。

注：下标从1开始

j12345678模式串abaabcacnext[j]01122312

KMP代码

int Index_KMP(string S, string T, int pos)
{
	//利用模式串T的next函数求T在主串S中第pos个字符之后的位置
	//其中T非空，1