数据结构––kmp算法(串)

kmp算法作为串的一个重要内容，必然有一定的难度，而在看到各类教辅书里的概念与解释后，其晦涩难懂的内容直接劝退一部分人，现在，让我们来看看吧

KMP解决的问题类型

KMP算法的作用就是在一个已知的字符串中查找子串的位置，就是串的匹配模式。比如，主串a = “cabcabcde”，子串b = “ab”。而我们就是要在a中找b的位置，那么这么看来是很简单的，但是，如果是字符串很长的时候呢？这样找起来就很麻烦了。接下来就介绍2种方法。

方法一：暴力求解法（BF算法）

从主串a和子串的第一个字符开始，将2个字符串的字符一一匹配，如果不匹配，主串就从第二个字符，子串从第一个字符开始再次匹配，如果不匹配，就从主串第三个字符，子串第一个字符开始。

那么，暴力求解法为什么这么慢呢？因为回溯的次数太多了

方法二：

每一个字符前的字符串都有最长相等前后缀，而且最长相等前后缀的长度是我们移位的关键，所以我们单独用一个next数组存储子串的最长相等前后缀的长度。而且next数组的数值只与子串本身有关。
所以next[i]=j,含义是：下标为i 的字符前的字符串最长相等前后缀的长度为j。
我们可以算出，子串t= "abcabcmn"的next数组为next[0]=-1(前面没有字符串单独处理)