题目

  判断一个字符串中是否包含另一个字符串。

朴素算法

  首先我们想到的方法肯定是暴力破解也就是朴素算法,在字符串 s1 中截取长度与字符串 s2 长度相等的字符串与其比较,来判断字符串 s1 中是否包含字符串 s2。

    // 判断 s1 是否包含 s2 O(m*n)
    public static boolean contain(String s1, String s2) {
        char[] s1Char = s1.toCharArray();
        char[] s2Char = s2.toCharArray();
        for (int i = 0; i <= s1Char.length - s2Char.length; i++) {
            int temp = i;
            for (int j = 0; j < s2Char.length; j++) {
                if (s1Char[temp++] != s2Char[j]) {
                    break;
                }
            }
            if (temp - i == s2Char.length) {
                return true;
            }
        }
        return false;
    }

RabinKarp

  RabinKarp 算法是利用哈希值来判断字符串是否相等,利用指定哈希算法,计算字符串 s2 的哈希值。然后在字符串 s1 中截取长度与字符串 s2 长度相等的字符串,并计算其哈希值和字符串 s2 的哈希值进行比较,来判断字符串 s1 中是否包含字符串 s2。

    // 判断 s1 是否包含 s2 O(n*m)
    public static boolean contain(String s1, String s2) {
        long s2Hash = hash(s2);
        for (int i = 0; i <= s1.length() - s2.length(); i++) {
            long tempHash = hash(s1.substring(i, i + s2.length()));
            if (tempHash == s2Hash) {
                return true;
            }
        }
        return false;
    }

    // 计算指定字符串的哈希值,假如转换为31进制
    public static long hash(String str) {
        long hash = 0;
        // 哈希值的求法:c0*31^2 + c1*31^1 + c2*31^0  == ((0 + c0) * 31 + c1) * 31 + c2
        for (int i = 0; i < str.length(); i++) {
            //hash += Math.pow(31, str.length() - 1 - i) * str.charAt(i); 该表达式和下面的表达式等价
            hash = 31 * hash + str.charAt(i);
        }
        return hash;
    }

RabinKarp 之滚动 hash  

  在上面的代码中,我们对 s1 的子串分别计算哈希值与 s2 的哈希值进行比较来判断字符串是否相等。我们可以对计算哈希值的过程进行优化,利用滚动哈希的思想:下一个字符串的哈希值 = 前一个字符串的哈希值 + 添加字符的哈希值 - 删除字符的哈希值。

// 判断 s1 是否包含 s2 O(n+m)
    public static boolean contain3(String s1, String s2) {
        long s2Hash = hash(s2);
        int n = s2.length();
        long[] res = new long[s1.length() - n + 1];
        // 前s2.length()个字符的hash
        res[0] = hash(s1.substring(0, n));
        for (int i = n; i < s1.length(); i++) {
            // 添加的字符
            char newChar = s1.charAt(i);
            // 删除的字符
            char deleteChar = s1.charAt(i - n);
            res[i - n + 1] = (long) (res[i - n] * 31 + newChar - Math.pow(31, n) * deleteChar);
        }
        System.out.println(Arrays.toString(res));
        System.out.println(s2Hash);
        for (long re : res) {
            if (s2Hash == re) {
                return true;
            }
        }
        return false;
    }

    // 计算指定字符串的哈希值,假如转换为31进制 
    public static long hash(String str) {
        long hash = 0;
        // c0*31^2 + c1*31^1 + c2*c1^0  == ((0 + c0) * 31 + c1) * 31 + c2
        for (int i = 0; i < str.length(); i++) {
            //hash += Math.pow(31, str.length() - 1 - i) * str.charAt(i); 该表达式和下面的表达式等价
            hash = 31 * hash + str.charAt(i);
        }
        return hash;
    }

标题:字符串匹配——RabinKarp
作者:Yi-Xing
地址:http://zyxwmj.top/articles/2020/05/05/1588691521381.html
版权声明:本文为博主原创文章,转载请附上博文链接!
博客中若有不恰当的地方,请您一定要告诉我。前路崎岖,望我们可以互相帮助,并肩前行!

添加新评论