并行系统中KMP串匹配算法的实现

李艳鵾，付维娜，刘 帅，祝 明

LI Yan-kun1，FU Wei-na2，LIU Shuai3，ZHU Ming1

（1.长春工业大学 工商管理学院，长春 130012；2.长春工程学院 软件学院，长春 130012；3.吉林大学 计算机科学与技术学院，长春 130021）

0 引言

字符串匹配算法作为字符串所有算法的基础，其重要性毋庸置疑，KMP算法以其为n的线性函数的时间复杂性而成为字符串匹配中的常用算法[1,2]，并一直使用至今。近年来也有很多关于KMP算法的研究[5,6]，取得了很好的结果，同时也有很多KMP在模式识别、模式匹配方面的成果[8,9]。

但是，KMP算法的时间复杂性一直无法得到有效的改善。为了改善KMP算法的复杂性，本文将KMP算法推广至并行机进行并行处理，以降低其时间复杂性。

并行处理采用多处理机对多进程进行并行处理，对很多传统算法的并行化已成为一个计算机领域的研究方向[3]。因此，如果能将KMP算法并行化，则可以大大降低其时间复杂性。

因此，本文在文献[4，7]的基础上，将KMP算法并行化，并通过加入冗余串来解决KMP算法的丢解情况，并得出实验数据。通过实验可知，本算法可以在不降低代价的前提下，对KMP算法进行优化，并且其效率和扩展性均良好。

本文的贡献在于：1）对KMP的并行化有效的降低了匹配时间；2）并行化算法的效率和扩展性良好，已达到并行的最优界限。

1 并行算法参数设置

1）运行时间t（n）=tr+tc，其中tr为数据经由网络或存储器的选路时间，tc为数据在处理器内部进行算术、逻辑运算所需的计算时间。

2）处理器数目p（n），求解问题所需的处理器数目，通常p随问题规模n变化函数为p（n）=n1-e（0＜e＜1）。

3）并行算法代价c（n）=t（n）·p（n），若解决某一问题的并行算法的执行代价与最坏情况下串行算法的运行时间（步数）同阶，则称其为代价最佳。……