专栏首页云霄雨霁子字符串查找----Boyer-Moore算法(从右向左匹配)

子字符串查找----Boyer-Moore算法(从右向左匹配)

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)相等,就是找到了匹配。否则匹配失败,失败有三种情况:

  1. 如果造成失败的字符不包含在模式字符串中,则将模式字符串向右移动j+1个位置;
  2. 如果造成失败的字符包含在模式字符串中,根据right[]数组右移模式字符串;
  3. 如果这种方法无法增大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;              
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 字符串查找----查找算法的选择

    SuperHeroes
  • 加权有向图----加权有向图的实现

    SuperHeroes
  • Mybatis--入门实例

    SuperHeroes
  • 如何从最坏、平均、最好的情况分析复杂度?

    但是,如果遵循严格的渐近分析法,需要掌握大量数学知识,这无疑给我们评估算法的优劣带来了很大的挑战。

    彤哥
  • (2)交换排序之冒泡排序

    title: (2)交换排序之冒泡排序 date: 2019-02-10 13:00:00 +0800 update: 2019-02-10 13:00:...

    suveng
  • 【LeetCode第20场夜猫赛】5323. 根据数字二进制下 1 的数目排序

    给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。

    韩旭051
  • java基础第二篇

    1.应用场景:判断四季(春夏秋冬),判断星期,根据用户的选择,进行对应的操作

    海仔
  • Leetcode Golang 106. Construct Binary Tree from Inorder and Postorder Traversal.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/arti...

    anakinsun
  • 2017第八届蓝桥杯决赛(C++ B组)4.发现环

    小明的实验室有N台电脑,编号1~N。原本这N台电脑之间有N-1条数据链接相连,恰好构成一个树形网络。在树形网络上,任意两台电脑之间有唯一的路径相连。 不过在最...

    racaljk
  • 冒泡排序

    通过对数组序下标最小的元素开始,依次比较相邻元素的值,如果发现逆序则交换,使值较大的元素逐渐向后移。如果一趟中没有进行过交换,就说明序列有序了,因此要在排序过程...

    桑鱼

扫码关注云+社区

领取腾讯云代金券