Boyer-Moore算法
通过学习和借鉴之后，感觉这个算法思想挺精妙，同时也比较复杂。我根据自己的理解写了一个算法，望大家指教。
前面提到过，这个算法是从右往左匹配，根据“坏字符规则”和“好后缀规则”来跳转，避免无谓的比较。
坏字符规则
这个规则比较简单，首先看pat的末位是不是和要查找的文本匹配，如果不匹配，pat里面又没有这个字符，则可以完全跳过这个字符，如下图：
如果pat里面有这个字符，则跳到pat里面最右的这个字符（当然排除自己），如下图中pat的第二个T:
可见这个规则是在末位就不匹配的时候用的，如果已经匹配了几位了，这几位就是“好后缀”了。
好后缀规则
个人觉得，如果要清晰理解这个规则，应该再明确两个概念，一个是“中缀”、一个是“前缀”。
中缀
如下图，在pat＝wowwow中，第3位的w就是中缀，它有两个特点：一是和后缀匹配；二是它前面的字符不能和“后缀”前面的字符一样，否则跳转过去没意义。
下图中，如果匹配到4的时候发生miss match，就跳到2，换个w来比。
另外要注意的是，中缀可能很多，在BM算法中就考虑移动到最右边的这个中缀，如下图，x y 的中缀出现了好多次，如果在8出现mis match，就跳到5，而不考虑2了。
注意，最前面的x y不算中缀，而算“前缀”。
前缀
和后缀匹配的前缀这里简称“前缀”。如果pat＝wowwow，其前缀是w 和wow，长度分别为1 和 3，这说明前缀长度可以是跳跃的，长度为2的前缀不存在。
如AAAcAAAAAAcAAA的前缀长度就有7、3、2、1。
最后，在前缀跳转和中缀跳转中，应该取小的，避免遗漏（中缀跳<前缀跳）。
如果中缀、前缀都不存在，就可以直接跳过整个已经匹配的部分。
算法实现
坏字符表构造
坏字符表理论上可以用哈希表来做，不过我实验了下，字符比较本来运算量就小，用哈希有点费，还是改用数组了，cJump 是坏字符跳表，由于不知道字符集的大小，这里用动态扩展策略。
其中，m = pat.Length;
static List<int> cJump = new List<int>();
static void BuildCharJump()
{
cJump.Clear();
for (int i = 0; i < m - 1; i++)
{
var k = (int)pat[ i ];
while (k >= cJump.Count) cJump.Add(m);
cJump[k] = m - 1 - i;
}
}
好后缀表构造
好后缀表又称为match jump，可以通过上次帖子介绍的“逆向的MP fail links”来构造，因为是倒着匹配的。
为了便于理解，这里给出一个“逆向MP fail links”的构造过程：
static int[] mJumps;
static void BuildMatchJump()
{
if (m < 2) return;//少于一个字符，不存在后缀
//一、初始化
var n = m - 1;
mJumps = new int[ n ];
for (int k = 0; k < n; k++)
mJumps[ k ] = (n - k) + m;//初始化为最大移动数
//二、构造逆向 MP fail links，并计算中缀跳表
var fails = new int[ m ];//逆向 MP fail links
int i = n;
int j = fails[ n ] = m;
while (true)
{
while (j < m && pat[ i ] != pat[ j ])
{
if (j < n)// 已匹配长度 + 移动数
mJumps[ j ] = Math.Min(mJumps[ j ], (n - j) + (j - i));//计算中缀跳，记录最右的中缀
j = fails[ j ];
}
if (i == 0) break;
fails[--i] = --j;
}
//三、计算前缀跳表
var s = 0;
while (j < m)//顺着最后一个箭头往前可找到所有前缀
{
if (pat[ i ] == pat[ j ])
{
var L = m - j;//前缀长度
for (int k = s; k < m - L; k++)//已匹配长度 + 移动数
mJumps[ k ] = Math.Min(mJumps[ k ], (n - k) + (m - L));
s = m - L;
}
j = fails[ j ];
}
}
查找算法
最后的查找算法再用两个表就好了：
static public int IndexOf(string pattern, string text, int index)
{
if (pat != pattern)
{
pat = pattern;
BuildCharJump();
BuildMatchJump();
}
int i = index + m - 1, j = m - 1;
while (i < text.Length)
{
if (j < 0) return i + 1;//找到
if (pat[ j ] == text[ i ]) { i--; j--; }
else
{
if (m - j == 1)//末位不匹配
{
var k = (int)text[ i ];
if (k < cJumps.Count) i += cJumps[ k ];
else i += m;
}
else i += mJumps[ j ];
j = m - 1;
}
}
return -1;
}
后记
个人觉得MB算法还可以有改进的地方：可以提出一个“坏后缀规则”，因为MB算法构造跳表的时候没有考虑text的内容，所以没办法知道“坏后缀”，明天咱们继续分析这个改进。