KMP算法之我见

1.KMP算法中的模式串前提条件是非常短，相对于匹配串忽略不计。在大多数情况下，的确如此。

当一个模式串 T 中某一个位置j与匹配串S中的位置i不同时，不对i进行回溯。因为模式串中第j个位置之前的串

【t0,t1,...tj 】

与S中从 j-i 到 j的子串【s(j-i), s(j-i + 1)...,sj】 肯定是相同的。

既然【t0，t1,...tj】的信息是提前知道的，并且一般情况下T串比较短，因此我们可以对T串进行预处理。

既然t串是已经知道的。需要平移多少才可继续比较肯定可以算出来。

无非就是平移1,2，。。j这样。这就包含了所有的情况，平移1，则Si与T-1比较。平移2，Si与Tj-2比较。

那么平移j就是 Si与T0进行比较。

 

这样查找T串的时间复杂度就会降低。当然如果每一次T串都不同，并且T串很长，预处理的时间其实也很长，整体算法并不能起到优化的作用。

因为next函数占去了大部分的时间。跟普通的匹配算法没有区别。

2.String.java中的indexOf就没有采用kmp算法。我估计就是这个原因。作为一个对外接口来说，不可能每次都预处理并存起来，所以每次都要预处理字符串。这就造成kmp算法在String中作为对外接口不适用性。

3.在大篇幅查找中。例如linux的grep函数，使用这种算法可以显著提高查找效率。如果结合索引技术，查询效率可以得到质的飞跃。