KMP算法那些事

前言众所周知，字符串匹配暴力方法时间复杂度过大。经典的看毛片算法(KMP)算法，使用预处理的手段和后缀前缀特征以及递归思想，可以大幅度优化字符串匹配时间复杂度。KMP算法思路

KMP就是每回模式串移动的不是一个单位移动，而是将前面匹配的都移动使得首部对应被匹配的字符串对应位置。也即是模式串得移动等同模式串移动块大小的位置。

模式串移动块即字符串后缀与字符串前缀的最大共同部分。

利用递归的思路预处理求解模式串移动块 从第一个位置开始循环 ，标记为q，当k位置的元素不等于q位置的元素，k递归为next[k-1],相等时k后移，使得next[q]=k;

跟据next数组进行移动模式串，递归求解。

KMP模式串移动块.png

实现代码预处理next数组

KMP核心代码

next数组详解举个例子

kmpnext数组举例子.png

例子图片和代码走一遍 了然于心