A New Start

字符串匹配算法(一)KMP

一、经典介绍

      字符串匹配,顾名思义,就是在给定的长串字符串中,查询指定的搜索词出现的位置。身为 Java 开发人员的我接触的最原生并广泛的便是 Java 中 String 字符串中的 indexOf() 方法。

      Java 中的 indexOf 方法,其算法便是使用的最易懂、最普世的 BF(Brute Force) 算法,即“暴力检索”。

      实现原理见下图描述:

KMP01.png

       实现代码的话,详见 java.lang.indexOf() 方法即可。

二、KMP简介

       其实,上述的 BF 算法的时间复杂度为O(mn),有很多性能更强的字符串匹配算法比其优秀,对于 Java 的优化,比如 hashmap 等数据结构在 Java8 中都得到了再次的性能提升,但是 String 中的字符串匹配却一直使用此种算法,很是好奇为什么?网上看到很多的言论,但是令人信服的有两点:其一便是“常用场景”,即字符串很多场景下的规模并不大,使用 BF 已经足够了,其二便是在其一的基础上,由于使用 BF 并不需要额外的初始化时的时间和空间开销,所以在“常用场景”之下,足矣。或许在将来的某个版本之上会有改变,但是再言之,据说其实 JVM 有内部的优化,此点暂未考量过。

       所以,既然 BF 有劣势,那么就肯定有性能更好的选择,此文介绍的 KMP(Knuth-Morris-Pratt) 便是其一,其是在 BF 的基础上进行的改良。

三、实现

       其实,KMP 的算法逻辑并不难理解,见下图就能够明白。

        KMP02.png

       但是关键点在于,我们的搜索词到底该往后移几位呢?这里面有涉及另一样有趣的玩意儿,下面会介绍。

四、next 数组

       其实,我们前文提过,为什么 Java 中的indexOf 仍采用 BF 算法的原因之一有可能是因为,在量级并不大的 String 之下使用 BF,有效地规避了时间和空间上的初始化成本,反言之,KMP 算法是需要初始化的,那么初始化成什么样?如何初始化?这里其实就是我们要讲的 next 数组,也就是上图中搜索词到底需要往后移多少位的问题的解答。

       在此之前,我们先了解两个概念,“前缀”和“后缀”,前缀即除最后一位以外的其余字符组成的字符串,后缀相反。

       如“ABCD”,前缀有“A”、