用Java实现字符串匹配的KMP算法

以下是在阅读 字符串匹配的KMP算法 后的代码实现。

未使用KMP

即朴素算法，或暴力算法，依次循环遍历字符串，如果不匹配则从子字符串的首位 + 1处开始再次遍历。

使用了KMP

KMP算法对朴素算法的优化点在于，省去了一些不必要的遍历。朴素算法在不匹配时会回到子字符串首位 + 1的位置，而KMP会从子字符串 + n的位置开始，n的值由字符串动态确定：

对于KMP算法，可先生成部分匹配表，在搜索中直接查表，或者向上面代码那样，使用一个next()函数，根据传入的字符串和位置索引，返回相应的部分匹配值。

KMP算法的实现代码与朴素算法的实现代码只有两处不同，一处是朴素算法为i = i - j + 1，KMP算法为i = i - j + move，move根据相应计算规则得到。另一处是新增了next()方法，这也是必然的，因为move的取值基于next()方法。

性能测试

KMP算法相比朴素算法真的有性能上的提高吗？写代码来测试一下。

首先是普速算法使用的T类，修改主方法：

这里生成了一个很长的字符串，长度为BBC ABCDAB ABCDABCDABDE的长度乘以1后面6个0。

运行代码，输出的数字单位为毫秒，不同的硬件配置运行效率不同。我的测试结果基本浮动在120ms ~ 150ms之间。

用同样的方式测试使用了KMP算法的KMP类，只需修改上面相应的调用语句为：

程序运行时间浮动在50ms左右。