KMP算法初学

具体讲解https://blog.csdn.net/v_JULY_v/article/details/7041827

两个概念得需要知道：

前缀：指的是字符串的子串中从原串最前面开始的子串，如abcdef的前缀有：a,ab,abc,abcd,abcde
后缀：指的是字符串的子串中在原串结尾处结尾的子串，如abcdef的后缀有：f,ef,def,cdef,bcdef

如果给定文本串S“BBCABCDABABCDABCDABDE”，和模式串P“ABCDABD”，

普通的方法就是暴力，从头开始遍历如果不匹配就让字串向后平移一位，平且需要重新开始对比，重复此过程直到找到对应的字串，非常耗时。

KMP算法不需要重新对比，只需要找到最长的公共前后缀然后将前缀移至后缀，并且继续从字串的当前位置开始比较，比如两个串，主串abbababaabbab，模式串abbaa,我们从1开始遍历（红色表示不匹配，蓝色表示最长公共前缀后缀）

1.abbababaabbab

   abbaa

第五位不同，且最长公共前缀后缀长度为1，将模式串前缀移至对应的后缀上，继续从第五位开始比较不需要回溯，不断的重复直到找到对应的子串：

abbababaabbab

      abbaa

……（这是我理解的）

next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next [j] = k，代表j 之前的字符串中有最大长度为k 的相同前缀后缀。此也意味着在某个字符失配时，该字符对应的next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next [j] 的位置）。如果next [j] 等于0或-1（0代表没有，-1代表就不存在前缀后缀），则跳到模式串的开头字符，若next [j] = k 且 k > 0，代表下次匹配跳到j 之前的某个字符，而不是跳到开头，且具体跳过了k 个字符，next 数组相当于“最大长度值” 整体向右移动一位，然后初始值赋为-1。

//优化过后的next 数组求法