KMP算法中的优化应用探讨

无回溯的模式匹配中最具代表性的是KMP算法。它是基于对模式本身的字符分布特征所进行的分析,生成模式的特征向量,并在模式匹配的过程中对此加以利用,以提高模式匹配的效率,其时间代价是目标串长度的线性函数,同时模式的特征向量的计算也与模式本身长度成正比。在KMP算法中最关键的部分是模式的特征向量的计算和生成。