单模式精确匹配算法研究

Study of single pattern exact matching algorithms

模式匹配算法在各领域中有重大的应用价值。文章详细分析了BF、KMP、BM、Tuned BM和QS 5种单模式精确匹配算法;通过上机实验,采用不同的模式串长度对这些算法的匹配次数、比较过的字符个数和所需时间3方面进行测试;结果表明,BM、Tuned BM、QS算法在实际运行性能相对较好;而Tuned BM算法可有效地减少字符比较次数,是其中时间复杂最优的算法。

Presented in the paper is a detailed analysis of five single pattern exact matching algorithms including the Brute-Force（BF） algorithm,the Knuth-Morris-Pratt（KMP） algorithm,the Boyer-Moore （BM） algorithm,the Tuned BM algorithm and the Quick Search（QS） algorithm. Some experiments are made in which the attempted times, character comparisons and needed time of these algorithms are tested through using different length of pattern strings. It is concluded that the performance of the BM, Tuned BM and QS algorithms is satisfactory in actual operation. The Tuned BM algorithm is the quickest one among these algorithms because it can reduce character comparisons effectively and shorten the time.