一种快速的单模式匹配算法

Faster algorithm for single pattern matching

在对Boyer-Moore(BM)算法及其改进的Tuned Boyer-Moore(TunedBM)算法进行分析的基础上,提出了一种更加快速的单模式匹配算法——NFS。该算法利用当前尝试中匹配失败字符的位置信息进行更大的尝试位置移动,使算法具有更高的效率。实验结果表明,NFS算法的性能优于同类的其他算法,特别是在模式长度较短的情况下,优势更为明显。

This paper proposed a more efficient algorithm, NFS algorithm, based on the ideas of Boyer-Moore（BM） algorithm and Tuned Boyer-Moore（TunedBM） algorithm for single pattern matching. NFS used the mismatch information to increase the shift distance so that it was more efficient. The experimental results show that the algorithm is superior to other algorithms for pattern matching. Especially, when the pattern is small, it is more efficient than other algorithms.