查找字符串之boyer-moore算法

1 问题的提出

给出字符串P和T，长度分别为n和m。找出P在T中出现的所有位置。

2 原始匹配算法

int Index(char* P,char* T,int pos)
{
	i = pos; j = 0;
	while( i<=strlen(T) && j<=strlen(P) ){
		if(P[j] == T[i])  {++i;  ++j;}
		else  {i -= j;  j = 0;}
}
if(j> strlen(P))  return (i – strlen(P) + 1);
else    	      return -1;
}

    上述算法的最坏时间复杂度为O(mn)。boyer-moore算法、KMP算法、suffix tree算法(后缀树)能够在线性时间内处理的字符串的匹配问题。
    suffix tree算法需要对字符串T进行预处理，而boyer-moore算法和KMP算法需要对P进行预处理。所以，suffix tree比较适合T不变，P变化的场景。boyer-moore算法和KMP算法适合T变化，P不变的场景。本文即是对boyer-moore算法的理论性介绍。

3 字符串匹配算法之boyer-moore算法

3.1 从右到左扫描

    在进行一次的匹配过程中，扫描P是从右向左的。如下图，在第一次的匹配过程中，首先比较P[7]和T[7]，然后比较P[6]和T[6]，从右向左滑动。

3.2 坏字符规则

    见图2。第一次比较：T[7](=x) ≠ P[7](=a)，结果是不匹配，此时如果我们知道x在P中出现的right-most位置为4，就可以移动P至图3中所示的位置。

定义：
字符集中的任一字符x，R(x)表示在P中出现的right-most位置，如果x没有在P中出现，则R(x)置为0。计算R(x)的时间复杂度为O(n)。

坏字符规则：
在某次匹配过程中，P的最右边的 n-i 个字符已经和T中的匹配，但是第i个字符不匹配(对于T中的第k个字符)，此时P应该向右移动 max( 1, i – R(T[k]) )。

坏字符规则在实际应用中特别高效。但是如果字符集比较小，则效率较差，时间复杂度达不到线型。

3.3 好后缀规则

好后缀规则：
    在某次的匹配过程中，P的一个后缀匹配了T中的的子串t，但是子串t左边的第一个字符不匹配，如果P中存在满足如下条件的子串t`：
1 t`=t，但t`不是P的后缀
2 在P中位于t`左边的第一个字符 ≠ 在P中位于t左边的第一个字符
3 在满足第1，2条件下，在P中位置处于最右的t`
    则移动P使得t` 与T中的t对齐，如图5所示。如果不存在，则向右移动P最少距离，使得P的某个前缀匹配T中的t的某个后缀，如图6。如果还没有匹配的，则P向右移动n个位置，如图7。

【定义】
对于任一i∈(1,n)，L(i) 是满足下列条件的值：
1 L(i) < n
2 字符串P[i…n] 匹配P[1…L(i)]的后缀
3 如果存在满足条件1和2的情况，则取最大值 ，否则取值为0

【定义】
Nj(P)是 满足如下字符串的长度：
1 是P[1…j]的后缀
2 是P的后缀
3 满足条件1，2的最长字符串

【定理】
L(i) 是 满足条件Nj(P) = |P[i…n]|= n–i +1 的j的最大值。
根据如上定理，计算L(i)的算法如下：

for i:=1 to n do L(i) := 0;
for j:=1 to n-1 do
	begin
	i:=n - Nj(P) + 1;
	L(i) = j;
	end;

3.4 完整的boyer-moore算法

    在3.2和3.3节中，给出了2个移动的位置。在boyer-moore算法中，取2个值中的最大值。

3.5 复杂度分析

    在坏字符规则中，计算R(x)的时间复杂度为O(n)；在好后缀规则中，计算L(i)的时间复杂度为O(n)。所以boyer-moore算法的时间复杂度为O(m＋n)。

4 KMP算法

    假设主串为s1 s2 …sn 模式串为p1 p2…pm 。当匹配过程中产生失配(即si≠pj)时，模式串向右滑行多远，换句话说，当主串第i个字符与模式串中的第j个字符发生失配时，主串中的第i个字符(i指针不回溯)应用与模式中的哪个字符比较？
next[j] = 0  当j=1
     = Max{k| 1<k<j 且 p1…pk = pj-j+1…pj-1 }
=1 其它情况
    复杂度分析。计算next数组的复杂度为O(m)，所以最终匹配的复杂度为O(m+n)。