KMP算法解决的基本问题是检查两个字符串，子串是否包含在主串中，并找出出现的位置。

对于字符串匹配，其实不难想到暴力的解法，分别用指针i，j遍历主串str1和子串str2。当str1[i]和str2[j]不同时，i返回当前匹配起始位置的下一个的位置，j变回0。不难发现，这样的算法并不高效，其时间复杂度为O(mn)，m，n分别为主串和子串的长度。由此我们引入KMP算法来以更高的效率解决字符串的匹配问题。

通过观察暴力解法的过程可以知道，造成暴力解法效率低下的一个重要原因是主串上的指针i在每轮结束后都要回到开头。使得在遍历过程中在i好多地方一直重复的遍历，这造成了极大的浪费。能不能想一种办法让i不走回头路呢？它就是公共前后缀！！！

公共前后缀是KMP算法的核心，每次匹配失败后可以直接根据公共前后缀直接移动子串上的j指针并跳过拥有公共前后缀的部分，这样一来，主串上的指针i就可以一直往后遍历，极大提高了算法的效率。

而下面是next数组的构建，我们会根据next数组来确定每次失配后子串上指针的移动位数。

next数组的长度与子串长度一致，next数组的每一个元素储存这位之前的子串公共前后缀长度。例如：子串str2=“aabaaf”。next[0]为字符串"a"的公共前后缀为0，next[1]为字符串"aa"的公共前后缀为1.......next[4]为字符串"aabaa"的公共前后缀为2，next[5]为字符串"aabaaf"的公共前后缀为0。

这里分享一个视频，里面介绍了KMP算法的匹配过程和求出next数组的方法。

https://www.bilibili.com/video/BV18k4y1m7Ar/