Rabin Karp 算法

用 R 表示数字的进制数，用 L 表示数字的位数，就可以总结出如下公式：

/* 在最低位添加一个数字 */
int number = 8264;
// number 的进制
int R = 10;
// 想在 number 的最低位添加的数字
int appendVal = 3;
// 运算，在最低位添加一位
number = R * number + appendVal;
// 此时 number = 82643

/* 在最高位删除一个数字 */
int number = 8264;
// number 的进制
int R = 10;
// number 最高位的数字
int removeVal = 8;
// 此时 number 的位数
int L = 4;
// 运算，删除最高位数字
number = number - removeVal * R^(L-1);
// 此时 number = 264

如果你能理解这两个公式，那么 Rabin-Karp 算法就没有任何难度

187 题「重复的 DNA 序列」

我简单描述下题目：

DNA 序列由四种碱基 A, G, C, T 组成，现在给你输入一个只包含 A, G, C, T 四种字符的字符串 s 代表一个 DNA 序列，请你在 s 中找出所有重复出现的长度为 10 的子字符串。

比如下面的测试用例：

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]
解释：子串 "AAAAACCCCC" 和 "CCCCCAAAAA" 都重复出现了两次。

输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]

函数签名如下：

List<String> findRepeatedDnaSequences(String s);

题解：

List<String> findRepeatedDnaSequences(String s) {
    // 先把字符串转化成四进制的数字数组
    int[] nums = new int[s.length()];
    for (int i = 0; i < nums.length; i++) {
        switch (s.charAt(i)) {
            case 'A':
                nums[i] = 0;
                break;
            case 'G':
                nums[i] = 1;
                break;
            case 'C':
                nums[i] = 2;
                break;
            case 'T':
                nums[i] = 3;
                break;
        }
    }
    // 记录重复出现的哈希值
    HashSet<Integer> seen = new HashSet<>();
    // 记录重复出现的字符串结果
    HashSet<String> res = new HashSet<>();
    
    // 数字位数
    int L = 10;
    // 进制
    int R = 4;
    // 存储 R^(L - 1) 的结果
    int RL = (int) Math.pow(R, L - 1);
    // 维护滑动窗口中字符串的哈希值
    int windowHash = 0;
    
    // 滑动窗口代码框架，时间 O(N)
    int left = 0, right = 0;
    while (right < nums.length) {
        // 扩大窗口，移入字符，并维护窗口哈希值（在最低位添加数字）
        windowHash = R * windowHash + nums[right];
        right++;

        // 当子串的长度达到要求
        if (right - left == L) {
            // 根据哈希值判断是否曾经出现过相同的子串
            if (seen.contains(windowHash)) {
                // 当前窗口中的子串是重复出现的
                res.add(s.substring(left, right));
            } else {
                // 当前窗口中的子串之前没有出现过，记下来
                seen.add(windowHash);
            }
            // 缩小窗口，移出字符，并维护窗口哈希值（删除最高位数字）
            windowHash = windowHash - nums[left] * RL;
            left++;
        }
    }
    // 转化成题目要求的 List 类型
    return new LinkedList<>(res);
}

其主要妙处是使用窗口滑动算法，结合将字符串数字化的逻辑，提高字符串的匹配效率从而提高效率

28. 找出字符串中第一个匹配项的下标

标准 RK 算法

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

题解：

class Solution {
    public int strStr(String haystack, String needle) {
        int nlen = needle.length();
        int R = 256;
        //设置超大的素数Q来降低哈希冲突
        long Q = 1658598167;
        long RL = 1;
        //通过求模来计算RL，否则得出的数会过于庞大
        for(int i = 1; i < nlen ; i++){
            RL = (RL*R) % Q;
        }

        //计算neeedle的哈希值
        long needleHash = 0;
        for(int i = 0 ; i < nlen; i++){
            needleHash = (R*needleHash + needle.charAt(i)) % Q;
        }

        int left = 0;
        int right = 0;
        int hlen = haystack.length();
        long windowhash = 0;
        while(right < hlen){
            //计算haystack的哈希值
            windowhash = (R*windowhash + haystack.charAt(right)) % Q;
            right++;

            if(right - left == nlen){
                //由于哈希冲突，进行两次判断是否为对应的字符串，反正这里不会出现哈希冲突
                if(windowhash == needleHash){
                    if(needle.equals(haystack.substring(left,right))){
                        return left;
                    }
                }
                //不符合，就将做左侧数字移出窗口
                windowhash = (windowhash - (haystack.charAt(left)*RL)%Q + Q) % Q;
                left++;
            }
        }
        return -1;
    }
}