Boyer-Moore算法——“坏后缀规则”？
如前贴所述，BM算法的“好后缀规则”实际上有两种情况：“中缀”和“前缀”。
“前缀”没啥问题，但是我发现“中缀”往往会出现“跳转以后朝向注定的失败匹配”，如下图所示：
如上图，在第6位X处发生了miss match，BM算法会跳转到3位，也就是将pat挪到如上表第三行的样子，再从11位开始比较，假设11～7都匹配成功了，但是X!=B，第6位是注定失败的。
那么可否将“中缀跳表”独立出来，匹配过程中判断”好后缀”加上它的前导字符构成的子串是否在pat中存在？如果不存在就是个“坏后缀”。
例如：上图中的“XXY”实际上是“坏后缀”，而不是“好后缀”，因为在pat中根本不存在这样的子串。
如何考虑“坏后缀规则”？
如果要实现这个规则，需要注意两个问题。
如下图，和前面一样，假设在倒数第三位X处发生了miss match，可以跳转到两个位置（如箭头所示），但是有一个跳转是重复的，A=A。
因此可以看出，如果要独立“中缀跳表”，需要考虑两个问题：
- 某位置的中缀跳转可能不止一个；
- 跳转中可能存在重复。如果出现重复，需要取最右边的那个。
很容易想到，满足这两个需求，用个哈希表恰好。
一种实现方法
将（二）贴中的计算中缀跳表的地方用一个函数AddInfixJump(i, j);代替，这个函数如下：
/// <summary>
/// 中缀跳表
/// </summary>
static Dictionary<char, int>[] iJumps;
static void AddInfixJump(int i, int j)
{
if (j < m - 1)//最后一位采用坏字符移动，这里不需要
{
if (iJumps[ j ] == null) iJumps[ j ] = new Dictionary<char, int>();
//添加中缀跳 能保证从小到大
if (!iJumps[ j ].ContainsKey(pat[ i ])) iJumps[ j ].Add(pat[ i ], i);
}
}
这样去计算中缀跳表，能够保证没有重复，并且右边的跳转肯定是先计算的，所以保留的也是最右边的。
然后在搜索过程中，如果在pat倒数第1位以前发生了miss match（也就是不用“坏字符规则”）的时候，先设置跳转为原来的那个表（比原来少了中缀跳转而已），然后再看看是否有好的“中缀”：
shift = mJumps[ j ];//设置为前缀和坏后缀混合跳转
if (iJumps[ j ] != null &&//存在中缀
iJumps[ j ].ContainsKey(text[ i ]))//且跳转以后匹配text[ i ]
shift = m - 1 - iJumps[ j ][text[ i ]];//设置中缀跳 (m-1-j + j-k)
这样能够避免上面出现“注定的失败”了。
实验结果
通过实验我发现，这样改进以后，在随机字符串和英文文章的匹配中，比较次数能够降低10%～30％，但是总体性能提高却不明显。我估计性能肯定是损失在C#的泛型字典Dictionary<>上面了，“坏后缀”的思路应该很好，但是可能需要别的实现方法：比如字符集小的话可以用数组，或者别的语言实现。有人想到好方法麻烦告诉我：）
后记
这和我一直以来的编程经验是相反的：“一般来说，不应该先考虑太细节的优化，算法思想的优化是最重要的”；但是在字符匹配的程序中不完全是这样，字符比较的消耗很小，稍微复杂的逻辑和数据结构都会损失性能，所以凡事都有例外。
有些细节优化却能够提升性能，例如，原版的BM搜索过程是这样的：
var shift = 0;
var k = (int)text[ i ];
if (k < cJumps.Count) shift = cJumps[ k ];
else shift = m;
i += Math.Max(shift, mJumps[ j ]);
贴（二）中，我将其改为：
if (m - j == 1)//末位不匹配
{
var k = (int)text[ i ];
if (k < cJumps.Count) i += cJumps[ k ];
else i += m;
}
else i += mJumps[ j ];
实际上就是当匹配超过1个字符时候，不用去计算“坏字符跳”。这样小改动一点，在随机字符和英文测试中，性能都提高了10％左右。
当然要说明的是，MB算法总体性能相比最原始的BruteForce算法还是有大幅提高的，pat越长越明显。