分类： C/C++
2011-04-12 10:10:39
这是一个非常古老的话题，最近因为工作的原因，又翻了下字符串匹配算法，这一翻又翻出来新花样。
学过数据结构和算法的应该最熟悉的是著名的KMP算法，KMP利用模式串自身的匹配性质，在不匹配的时候可以跳跃比较长的距离，从而比之朴素的字符串算法速度快。
首先要说的是，据称该算法比KMP又快上3-5倍，该算法在Linux内核中有实现，详见Ts_bm.c，我用的内核版本是2.6.25，其他版本可能文件名有变。
BM算法我认为最大的改进在于从后往前比较，而不是大家熟知的惯例：从字符串的第一个开始，一个一个往后比。从后往前比较的优点是一旦遇到不匹配的时候，可以跳跃的距离更大，因为后面都不匹配了，前面再匹配都没有用了。另外一个亮点在于找不匹配的字符是否出现在模式串中，如果不出现可以直接跳过到该字符的后面。
这里不打算详细描述该算法，因为我给出的链接上有论文下载和KMP、BM算法的匹配过程演示，相信大家都看得明白。
不过看完后千万不要认为BM就是最好的字符串匹配算法了，这里要说的是另外一个算法，称之为Sunday算法，所谓“人外有人，天外有天”，该算法在BM的基础上再进行了改进，也证明了一句话：优化无止境。我也采用与BM主页上相同的例子来演示下其过程(空格我用下划线代替)：
我们要在"HERE_IS_A_SIMPLE_EXAMPLE"查找"EXAMPLE"，第一步，我们把模式串和文本串左边对齐：
pattern: EXAMPLE
text: HERE_IS_A_SIMPLE_EXAMPLE
我们依然从前往后比较，显然第一个就不匹配了，于是需要把模式串后移，但是后移多少呢，这个就是各个算法展示各自魅力的地方了：朴素算法是后移一位，KMP利用自身的匹配来移动，这里采取的方式是与BM有点类似，我们看文本串对齐后的下一个字符，也就是text中的'S'和'A'中的'_'，因为无论我们移动多少，这个字符总是要参与下一次匹配的，因为即使移动距离为1，这个字符也要参与匹配，因为如果把这个字符也跳过去了，那么就可能会漏掉可能的匹配，我们可以发现，在模式串中并不存在'_'这个字符，于是可以直接跳到'_'字符后面进行匹配，如下：
pattern: EXAMPLE
text: HERE_IS_A_SIMPLE_EXAMPLE
此时进行匹配，再次从左往右进行，第一个又不匹配，此时与上面一步一样，再看文本串的下一个字符，是'E'，该字符出现在模式串的最后一位，于是我们把文本串移动一位，把两个字符'E'对齐，此时得到如下：
pattern: EXAMPLE
text: HERE_IS_A_SIMPLE_EXAMPLE
再采取与上面同样的步骤，第一个不匹配，后面的字符'_'不在模式串中，于是移动到文本串对齐的下一位，得到下面的样子：
pattern: EXAMPLE
text: HERE_IS_A_SIMPLE_EXAMPLE
就这样，我们找到了匹配，看上去很简单吧，比BM算法匹配的次数还少，因为从思想来看每一步的移动量都会比BM大。算法的思想也非常好理解，至少比KMP好理解多了吧，至少我是这样认为，当年的KMP把人都搞晕了，为什么现在的教科书上不把更好的算法给出来呢，不说当前这个算法，至少BM总得提一提吧，郁闷的是我在《算法导论》上也没看到这算法的介绍。
代码就不给了，相信看的明白的人都能够很快的写出来的。
