一、字符串查找

算法题目链接 : 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)\mathrm{m}\mathrm{o}\mathrm{d}10^6$$

哈希表计算 :

计算 “abcde” 的子字符串哈希值 ,
先计算 “abc” 的哈希值 $x$ ,
然后计算 “abcd” 的哈希值 $(x\times 31+d)\mathrm{m}\mathrm{o}\mathrm{d}10^6$ , 然后将 “a” 的哈希值减掉 , $(x\times 31+d-a\times 31^3)\mathrm{m}\mathrm{o}\mathrm{d}10^6$ ;

这样就可以在 $O(1)$ 的时间内 , 得到 “abc” 的哈希值 , 然后在 $O(1)$ 的事件内得到 “bcd” 的哈希值 ;
被查找的字符串 “cde” 的哈希值是不变的 , 可以在开始计算出来 ;

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

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

遍历 $m$ 次 , 用于遍历外层字符串索引 , 哈希值计算复杂度为 $O(1)$ ,
那么 整体复杂度是 $O(m)$ ,
只有在哈希值相等的时候 , 才遍历 $n$ 个子字符串 , 复杂度是 $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);
    }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
 

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/119007903