KMP算法详解

初识KMP算法

KMP算法是为了解决什么问题？
看如下问题：
出自西安电子科技大学数据结构试题

首先我们要解决的问题就是找出第一个节点匹配位置
朴素解法即为
枚举原串S中的每个字符作为「发起点」，每次从原串的「发起点」和匹配串的「首位」开始尝试匹配：

匹配成功：返回本次匹配的原串「发起点」。
匹配失败：枚举原串的下一个「发起点」，重新尝试匹配。
图示如下：

时间复杂度为O（m*n）
m为串S的长度，n为T的长度
那么有没有办法将该过程的时间复杂度压到O（m+n）呢？
KMP算法就解决了这个问题

KMP算法希望在只遍历一遍数组的情况下找到匹配位置，所以对于串S指针i，我们需要让其不发生回退
实现思路如下

我们利用模式串T本身的特性获得了在i处匹配失败时我们应该从哪里继续匹配的问题，而不必回溯指针i

那么如何找出匹配失败后的回退位置呢这里我们就需要研究串T本身的性质