【字符串】字符串查找 ( Rabin-Karp 算法 )

韩曙亮

发布于 2023-03-29 14:52:52

1.1K0

发布于 2023-03-29 14:52:52

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

一、字符串查找

算法题目链接 : https://www.lintcode.com/problem/13/

在一个字符串中查找另外一个字符串第一次出现的位置 ;

如 : 在 “abcdefghijk” 中查找 “def” 第一次出现的位置 , 是

;

该方法使用暴力算法 , 两层 for 循环 , 肯定可以解决 ; 如果用暴力算法 , 那面试基本就凉了 ; 暴力算法的复杂度是

O(m \times n)

是第一个大字符串的长度 ,

是被查找的字符串长度 ;

KMP 算法是专门用于解决该问题的算法 , 该算法只能用于解决在一个字符串中查找另外一个字符串的问题 ; KMP 算法主要靠背诵 , 没有涉及到算法的理论 , 只能用于解决单一字符串查找问题 , 一般面试时不考虑使用该算法 ; KMP 算法的算法复杂度是

O(m + n)

;

Rabin-Karp 算法比 KMP 算法更简单 , 其基本原理就是比较字符串的哈希码 ( HashCode ) , 快速的确定子字符串是否等于被查找的字符串 ;

二、Rabin-Karp 算法

假设要在 “abcde” 字符串中 , 寻找字符串 “cde” ;

遍历时 , 如果使用蛮力算法遍历 , 先对比 “abc” 是否与 “cde” 相等 , 明显不等 , 继续遍历 , 向右平移一位 , 对比 “bcd” 与 “cde” 是否相等 ;

这里从 “abc” 平移到 “bcd” , 如果使用整个字符串比较的话 , 假如字符串的位数是

位 , 则复杂度是

O(n)

, 这里如果能将复杂度变为

O(1)

, 那么时间复杂度将大大降低 ;

两个

位的字符串比较 , 那么需要逐位对比 , 时间复杂度是

O(n)

, 这里使用哈希函数 , 对比两个字符串的哈希值 , 这样将时间复杂度降低为

O(1)

;

哈希函数 : 哈希函数可以将任何类型的数据 , 字符串 , 整型 , 字节等数据 , 转为整数 ; 哈希表是一个很大的数组 , 使用哈希函数 , 将某个字符串对应到哈希表中某个位置上 , 相同的字符串使用哈希函数计算的整数结果是相同的 ;

静置转换哈希函数 , 是最常用的哈希函数 ; 如 : “abcde” 的哈希码值为

a \times 31^4 + b \times 31^3 + c \times 31^2 + d \times 31^1 + e \times 31^0

是一个魔法值 , 使用该值效率最高 , 一般都设置这个数 ; 整个公式类似于组合数学中的生成函数 ; 这个结果很大 , 可能超过整数表示范围 , 为该值模一个较大的数 , 模的数越大 , 冲突的概率就越小 ;

(a \times 31^4 + b \times 31^3 + c \times 31^2 + d \times 31^1 + e \times 31^0) \mod 10^6

哈希表计算 :

计算 “abcde” 的子字符串哈希值 , 先计算 “abc” 的哈希值

, 然后计算 “abcd” 的哈希值

(x \times 31 + d) \mod 10^6

, 然后将 “a” 的哈希值减掉 ,

(x \times 31 + d - a \times 31^3) \mod 10^6

;

这样就可以在

O(1)

的时间内 , 得到 “abc” 的哈希值 , 然后在

O(1)

的事件内得到 “bcd” 的哈希值 ; 被查找的字符串 “cde” 的哈希值是不变的 , 可以在开始计算出来 ;

这里注意 , 哈希值相等 , 并不是代表字符串完全相等 , 理论上讲 , 有可能存在哈希值相等 , 字符串不相等的时候 , 虽然概率及其微小 , 建议在哈希值相等的情况下 , 再次判定一次字符串是否相等 ;

哈希码不同 , 则字符串一定不同 ; 哈希码相同 , 字符串不一定相同 ;

遍历

次 , 用于遍历外层字符串索引 , 哈希值计算复杂度为

O(1)

, 那么整体复杂度是

O(m)

, 只有在哈希值相等的时候 , 才遍历

个子字符串 , 复杂度是

O(n)

, 那么该算法的整体时间复杂度是

O(m + n)

;

class Solution {
    /**
     * @param source:
     * @param target:
     * @return: return the index
     */
    public int strStr(String source, String target) {
        if (target == null || source == null) {
            // 不符合规则, 直接返回 -1
            return -1;
        }

        // 计算哈希码
        int base = 1000000;
        int m = target.length();
        if (m == 0) {
            return 0;
        }

        // 计算 31^m
        int power = 1;
        for (int i = 0; i < m; i++) {
            power = (power * 31) % base;
        }

        // 计算被查找字符串哈希值
        int targetCode = 0;
        for (int i = 0; i < m; i++) {
            targetCode = (targetCode * 31 + target.charAt(i)) % base;
        }

        // 循环主体
        int hashCode = 0;
        for (int i = 0; i < source.length(); i++) {
            // 注意遍历的 i 用于计算哈希值
            // 哈希值代表的字符串的起始位置是 i - m + 1
            hashCode = (hashCode * 31 + source.charAt(i)) % base;

            // 如果不足 m 个字符, 不执行后续操作
            if (i < m - 1) {
                continue;
            }

            // 大于 m 个字符需要减去首位的哈希值
            if (i > m - 1) {
                hashCode = hashCode - (power * source.charAt(i - m)) % base;
                // 确保相减的结果是正数
                if (hashCode < 0) {
                    hashCode += base;
                }
            }

            if (hashCode == targetCode) {
                // 双重验证
                if (source.substring(i - m + 1, i + 1).equals(target)) {
                    return i - m + 1;
                }
            }
        }

        return -1;
    }
}

class Main {
    public static void main(String[] args) {
        int index = new Solution().strStr("mabcban", "cb");
        System.out.println(index);
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-07-22，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历