ACM 选手带你玩转 KMP 算法！( 二 ) _匹配

如果继续匹配下去的话，你会发现比较指针 i 在频繁的来回折返跑，就像上图第 1 次匹配的时候 i 已经走到了 5 ，等到了第 2 次匹配的时候 i 又回到了 1 。
这种动作叫做回溯，而造成暴力模式匹配效率低下的主要坏蛋就是频繁的比较指针回溯。
KMP 算法做到的就是比较指针不回溯，仅仅是后移模式串。
我们接下来看，这具体是怎么实现的。下面这部分要慢一点，好好体会。
还是以主串 S = ，模式串 T =为例。
上图是模式串与主串的第一次匹配，在 i = 5 ， j = 5 的时候出现不匹配的元素，在此之前的元素都是匹配的。
观察一下模式串，你会发现在匹配的部分里，存在相同前后缀的部分。
那第二步的匹配就可以像下图这样做，这也是 KMP 算法的核心。
看懂了么？前缀直接滑到了后缀的位置上。
为什么可以这么整呢？
因为在第 1 次的时候已经比较过了，在与主串完全匹配的部分里，模式串第 1 个和第 2 个元素与第 3 个、第 4 个完全一样。
此时主串的比较指针 i 继续从 i = 5 开始比较，模式串的比较指针 j 也不需要从 0 开始直接比较，可以从 j = 2 的位置开始比较。
你看去掉了很多无意义的匹配和回溯，大大提高了效率。
那么现在的问题成了每次不匹配的时候，找之前已匹配部分中，模式串的前后缀，而且还是最长公共前后缀。
也就是碰到某个不匹配的时候，我这个模式串要从最长前缀后滑动到最长后缀的位置（其实就是比较指针 j 从最长前缀移动到最长后缀的位置）。而保存这个位置的数组就是 next 数组。
求 next 数组值
next 数组的求解，一向是老大难问题，而且这玩意不只是在写代码的时候折磨人，大学的考试或者考研考试只要涉及数据结构与算法这门课，简直是必考题。
本来想写一下我之前一直常用的求 next 的方法，后来偶然看了 b 站up 主正月点灯笼的求法，感觉好像更容易理解一些，再此借鉴过来分享给大家。
在这以模式串 T = ababc 为例。
学校用的书呢，讲 KMP 的时候，大多数数组是从下标为 1 ，而不是 0 开始，所以为了更方便的讲解，这个例子的讲解我会默认数组是从下标为 1 开始的（如果你习惯从 0 开始，就是数组从 1 开始的结果每个值 -1 即可，下面会讲到）。
【ACM 选手带你玩转 KMP 算法！】（1）写出模式串 T 的各个前缀
（2）对于模式串 T 所有的前缀，找每一个前缀的最长公共前后缀。而且最长公共前后缀要比原始字符要短（如果一样长的话则没有意义，因为我们要的是滑动）。
在这里以 “abab”这个串为例，这时比较指针指向最后一位的时候，出现不匹配：
那么对于前 3 位 “aba” 来说，首先找长度为 2 的公共前后缀，最长前缀是 “ab” ，最长后缀是 “ba” ，显然前缀 ≠ 后缀；再来看长度为 1 的公共前后缀，最长前缀是“a” ，最长后缀也是“a” ，最长前缀 = 最长后缀，所以 “abab”这个最长公共前后缀的长度 = 1 。
正常来说，模式串的滑动就是从最长公共前缀 a 滑倒了最长公共后缀 a 的位置，比较指针 j 从 2 开始重新比较。