On lzq ways

字符串匹配算法总结

2019-05-30  本文已影响8人  zhengqiuliu

面写过一篇字符串匹配算法,总共涉及BF算法,RK算法,BM算法,还有一种算法是KMP算法。这几种算法思想和代码我都认真阅读完之后,发现BM算法和KMP算法还是很难完全掌握。如果自己闭卷再做一次这两种算法,我心里还是没有底气。

这两种算法思想都比较复杂,没有简单的数学公式可以依赖,场景较多,并且代码实现较为巧妙,很难用代码直观的表达算法思想。

假设主串A=ggusfsabxabcabxabxyyy, 长度为n 模式串B=abxabcabxabx 长度为m

BF算法:对A进行遍历,截取12长度的子串,子串和B进行逐个字符比较,如果完全相同则找到。算法思想简单直观,容易理解。但是如果比较的字符串长度较长时,这种算法的效率较低,时间复杂度=O(m * (n - m)) = O(m * n)

RK算法:和BF算法思想类似,需要提前设计好一个散列函数,把B转换为整数,然后把A中截取的子串也转换为整数,这样子串和B就可以直接通过整数进行比较,时间复杂度立刻降为O(n-m)。但是要设计一个好的散列函数,匹配各种类型是比较困难的。

下面再介绍两种重量级的算法BM和KMP

两种算法都是在比较子串时,不用一个一个字符移动比较,而是移动较大的位置,提高比较的效率。

BM算法

坏字符规则:模式串B与主串的子串C,B从后往前逐字符与C比较,如果遇到不相等的字符则记为坏字符。遇到坏字符处理方式:B继续从后往前对比寻找最近与坏字符相等的字符,如果找到则移动到对应位置;如果没有找到,则跨越整个模式串。从后往前找到相同字符,还分两种情况找到的字符可能在坏字符位置的前面,也有可能在后面。所以使用坏字符规则,移动的距离可能为负数,这个时候就需要另外一种规则好后缀规则。

好后缀规则:模式串B与主串对比遇到坏字符时,有一部分已经匹配好,这部分就叫做好后缀。B继续从后往前查询,如果还存在好后缀这样的子串,则移动到相应位置。如果不存在,就匹配好后缀最长的后缀子串,如果都无法匹配就跨越整个模式串。

最后每次从坏字符规则和好后缀规则中,获取较大移动位置的那个值,移动相应距离即可。

KMP算法:  模式串B与主串逐个字符对比,相同则一直往下比较。如果遇到不相等的字符,前面已经匹配好的字符串则为好前缀C。从好前缀中获取最大匹配好前缀子串的坐标,比较其后一个字符是否和坏字符相等,不相等继续直到循环终止。


BM算法如下:

/**

    *

    * @param a 主串

    * @param n 主串长度

    * @param b 模式串

    * @param m 模式串长度

    * @return

    */

    public int bm2(char[] a, int n, char[] b, int m)

    {

        int[] bc = new int[SIZE];

        generateBC(b,m,bc);

        int[] suffix = new int[m];

        boolean[] prefix = new boolean[m];

        generateGS(b,m,suffix,prefix);

        int i = 0;// j表示主串与模式串匹配的第一个字符

        while (i <= n - m){

            int j;

            for (j = m - 1; j >= 0 ; --j){

                if (a[i+j] != b[j]) break;// 坏字符对应模式串中的下标

            }

            if (j < 0){

                return i;

            }

            int x = j - bc[a[i+j]];

            int y = 0;

            if ( j < m-1){

                y = moveByGS(j,m,suffix,prefix);

            }

            i = i + Math.max(x,y);

        }

        return -1;

    }

    private void generateBC(char[] b,int m, int[] bc){

        for (int i = 0; i < SIZE; ++i){

            bc[i] = -1;

        }

        for (int i = 0; i < m; ++i){

            int ascii = (int)b[i];

            bc[ascii] = i; // 如果ascii相同只需要存储 bc[ascii] = 最后一个

        }

    }

    /**

    *

    * @param b = 模式串

    * @param m = 表示长度

    * @param suffix = 数组

    * @param prefix

    */

    private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix)

    {

        for (int i = 0; i < m ; ++i){ //初始化

            suffix[i]  = -1;

            prefix[i] = false;

        }

        for (int i = 0; i < m - 1; ++i){ // b[0,i]

            int j = i;

            int k = 0;

            while (j >= 0 && b[j] == b[m-1-k]){

                --j;

                ++k;

                suffix[k] = j + 1;//记录模式串每个可以匹配前缀子串的长度 等于 最大下标值

            }

            if (j == -1) prefix[k] = true;

        }

    }

    /**

    *

    * @param j 表示坏字符对应模式串中的字符下标

    * @param m 模式串长度

    * @param suffix

    * @param prefix

    * @return

    */

    private int moveByGS(int j,int m,int[] suffix, boolean[] prefix)

    {

        int k = m - 1 -j; // 好后缀的长度

        if(suffix[k] != -1) return j - suffix[k] + 1;

        for (int r = j + 2; r <= m-1; ++r){

            if (prefix[m-r] == true) return r;

        }

        return m;

    }


KMP算法如下:

/**

    * KMP算法

    * @param a

    * @param n

    * @param b

    * @param m

    * @return

    */

    public static int kmp(char[] a, int n, char[] b, int m)

    {

        int[] next = getNexts(b,m);//获取模式子串的最长前缀匹配子串的下表

        int j = 0;

        for (int i = 0; i < n; ++i){

            while (j>0&&a[i]!=b[j]){//模式串和主串不等,模式串对应下表为j, 匹配的前缀为最后下标为j-1, 获取j-1的最大匹配前缀,比较 前缀+1 和 坏字符是否相同即可

                j = next[j-1]+1;

            }

            if (a[i] == b[j]){//如果主串和模式串一样

                ++j;

            }

            if (j == m) return i - m + 1; // i是下标,m是长度 所有需要 i + 1 - m

        }

        return -1;

    }

    /**

    * b表示模式串,m表示模式串的长度

    * @param b

    * @param m

    * @return

    */

    private static int[] getNexts(char[] b, int m)

    {

        int[] next = new int[m];

        next[0] = -1; // 只有一个字符的前缀时,没有前缀

        int k = -1;

        for (int i = 1; i < m; ++i){ //遍历模式串 1 到 m-1

            /**

            * 如:模式串 ababacd.

            * i从[1,6],k从[0,5]

            * i = 1, k = -1 b[0] != b[1] => next[1] = -1

            * i = 2, k = -1 b[0] = b[2] ++k => next[2] = 0

            * i = 3, k = 0  b[1] = b[3] ++k  => next[3] = 1

            * i = 4, k = 1 b[2] = b[4] ++k => next[4] = 2

            * i = 5, k = 2 b[3] != b[5]  k = next[2] = 0, b[1] != b[5]  k = next[0] = -1 => b[0] != b[5] , next[5] = -1

            * i = 6, k = -1 b[0] != b[6] => next[6] = -1

            */

            while (k != -1 && b[k+1] != b[i]){ // 如果 在前基础上下个字符不相等时,就会比较最长比较子串的 最长匹配字串,就是次长匹配子串,直到找到为止

                k = next[k];

            }

            if (b[k+1] == b[i]){ // 思想next[2] = 0,表示 aba =》 a?ba? 只要 ?=?就会有 next[3] = 1

                ++k;

            }

            next[i] = k;

        }

        return next;

    }

上一篇下一篇

猜你喜欢

热点阅读