子字符串查找----Boyer-Moore算法

2018-01-27 10:27:44来源:oschina作者:Superheros人点击

分享

Boyer-Moore算法是一种从右向左扫描模式字符串并将它与文本匹配的算法。


举例说明Boyer-Moore算法:


有文本FINDINAHAYSTACKNEEDLE和模式字符串NEEDLE. 因为是从右向左扫描,所以会先比较模式中最后一位E和文本中下标为5的N。不匹配,因为模式字符串中也出现了N,则右移模式字符串使得模式中最右边的N(这里是位置0的N)与文本中的相应N对齐。然后接着比较模式字符串最后的E和文本中的S(下标10),不匹配,而且模式中不含有字符S,可以将模式直接右移6位,然后继续匹配......


上述方法被称为启发式的处理不匹配字符。要实现之,需要一个数组right[]保存字母表中每个字母在模式字符串中出现的最靠右的下标(如果不存在则为-1)。这个值揭示了如果发生不匹配,应该右跳跃多远。


在right[]数组计算后,算法实现起来就非常容易了。用一个索引i在文本中从左向右移动,用索引j在模式字符串中从右向左移动。内循环检查检查正文和模式字符串在位置i是否相等,如果从M-1到0的所有j,txt.charAt(i+j)都和pat.charAt(j)相等,就是找到了匹配。否则匹配失败,失败有三种情况:

如果造成失败的字符不包含在模式字符串中,则将模式字符串向右移动j+1个位置;
如果造成失败的字符包含在模式字符串中,根据right[]数组右移模式字符串;
如果这种方法无法增大i,就直接将i+1保证模式字符串至少向右移动一个位置。

在一般情况下,对于长度为N的文本和长度为M的模式字符串,该方法通过启发式处理不匹配的字符需要~N/M次比较。


public class BoyerMoore {
private final int R;
private int[] right;
private String pat;
public BoyerMoore(String pat) {
this.R = 256;
this.pat = pat;
right = new int[R];
for (int c = 0; c < R; c++)
right[c] = -1;
for (int j = 0; j < pat.length(); j++)
right[pat.charAt(j)] = j;
} public int search(String txt) {
int m = pat.length();
int n = txt.length();
int skip;
for (int i = 0; i <= n - m; i += skip) {
skip = 0;
for (int j = m-1; j >= 0; j--) {
if (pat.charAt(j) != txt.charAt(i+j)) {
skip = Math.max(1, j - right[txt.charAt(i+j)]);
break;
}
}
if (skip == 0) return i;
}
return n;
}
}

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台