2023年7月20日发(作者：)

BF,KMP,BM三种字符串匹配算法性能⽐较三种最基本的字符串匹配算法是BF，KMP以及BM，BF算法是最简单直接的匹配算法，就是逐个⽐较，⼀旦匹配不上，就往后移动⼀位，继续⽐较，所以⽐较次数很都。关于KMP和BM的详细介绍可以参考下⾯的两个link，是讲得⽐较好的。KMPBM理论上，BM具有最好的性能，因为⽐较的次数最好，其次是KMP，最差的应该是BF。今天对这三种算法做了⼀个简单的测试，测试程序运⾏在Windows 7 x64位系统上，四核CPU，32G内存，测试程序为x64。说明，只测试在⽬标字符串中找不到要搜索的字符串，以便能够遍历完所有字符串。测试1，在1亿个字符串（100M）搜索⼀个长度为20字节字符串，结果如下：BF spent time is 171(ms)KMP spent time is 422(ms)BM spent time is 15(ms)最快的是BM算法，花的时间也最少(15ms).测试2， 在10亿个字符串中（1G）中搜索⼀个长度为20字节的字符串，结果如下：BF spent time is 1670(ms)KMP spent time is 4321(ms)BM spent time is 203(ms)结果和测试⼀基本⼀致。通过这两次测试，很奇怪的是KMP算法居然⽐BF算法花的时间还多，说明KMP虽然理论上有很好的性能，但实际上很难有所作为，⼤多数情况下还不如BF算法。但是BM算法确实在⼤多数情况下都具有很好的性能体现。