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

文章目录

• 一、字符串查找
• 二、Rabin-Karp 算法

一、字符串查找

---

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

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

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

4

;

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

O(m times n)

,

m

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

n

是被查找的字符串长度 ;

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

O(m n)

;

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

二、Rabin-Karp 算法

---

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

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

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

n

位 , 则复杂度是

O(n)

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

O(1)

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

两个

n

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

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

31

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

(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” 的哈希值

x

, 然后计算 “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” 的哈希值是不变的 , 可以在开始计算出来 ;

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

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

遍历

m

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

O(1)

, 那么 整体复杂度是

O(m)

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

n

个子字符串 , 复杂度是

O(n)

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

O(m n)

;

代码语言：javascript复制

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);
    }
}

遍历 函数 面试 算法 字符串

0 人点赞