Rabin-Karp 算法

2020-07-01 约 3974 字预计阅读 8 分钟

见到好几次了，感觉不是很难，学一手，本来想详细的写一下完整的 Rabin-Karp 解析的，但是目前确实时间有点紧，加上自己也没做几题，理解的可能还不到位，等后面有时间再来补吧

1044. 最长重复子串

Difficulty: 困难

给出一个字符串 S，考虑其所有重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。

返回任何具有最长可能长度的重复子串。（如果 S 不含重复子串，那么答案为 ""。）

示例 1：

输入："banana"
输出："ana"

示例 2：

输入："abcd"
输出：""

提示：

2 <= S.length <= 10^5
S 由小写英文字母组成。

解法一

看题解区学习了一下，整体的思路倒是不难，主要就是一个rolling hash的过程，然后就是关于 MOD 的选取，到现在也不是很清楚怎么选 MOD。

public String longestDupSubstring(String S) {
    int n = S.length();
    int [] nums =new int[n];
    for (int i = 0; i < S.length(); i++) {
        nums[i] =  S.charAt(i) - 'a';
    }
    long MOD =  1L<<32;
    int B = 26; 
    int left = 1;
    int right = n - 1;
    int start = -1, mlen = 0;
    while (left <= right){
        int mid = left + (right - left)/2;
        int temp = RabinKarp(mid, B, nums, MOD);
        if (temp != -1){
            if (mid > mlen){
                mlen = mid;
                start = temp;
            }
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
    return start == -1 ? "" : S.substring(start, start + mlen);
}

public int RabinKarp(int len, int B, int[] nums, long MOD){
    //hash(S) = s[0] * B^(len-1) + s[1] * B^(len-2) + ... + s[n-1] *1
    //B^(len-1) （移除左端点时需要的值）
    long BL = 1;
    for (int i = 0; i < len - 1; i++){
        BL = (BL * B) % MOD;
    }
    //[0,len-1] 的 hash 值
    long h = 0;
    for (int i = 0; i < len; i++){
        h = (h * B + nums[i]) % MOD;
    }
    HashSet<Long> set = new HashSet<>();
    set.add(h);
    //rolling hash
    for (int i = 1; i <= nums.length - len; i++){
        //+MOD 是为了负数取模
        h = (h - nums[i - 1] * BL % MOD + MOD) % MOD;
        h = (h * B + nums[i + len - 1]) % MOD;
        if (set.contains(h)){
            return i;
        }
        set.add(h);
    }
    return -1;
}

解法二

补充一下冲突检测，猜 mod 也太玄学了😂

这个冲突检测的方法有问题，留下做个印证，正确的检测请直接看解法三

//写一波检测冲突的
public String longestDupSubstring(String S) {
    int n = S.length();
    long MOD = (long) 1e9+7;
    int B = 26; 
    int left = 1;
    int right = n - 1;
    int start = -1, mlen = 0;
    while (left <= right){
        int mid = left + (right - left)/2;
        int temp = RabinKarp(mid, B, S, MOD);
        if (temp != -1){
            if (mid > mlen){
                mlen = mid;
                start = temp;
            }
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
    return start == -1 ? "" : S.substring(start, start + mlen);
}

public int RabinKarp(int len, int B, String S, long MOD){
    //hash(S) = s[0] * B^(len-1) + s[1] * B^(len-2) + ... + s[n-1] *1
    //B^(len-1) （移除左端点时需要的值）
    long BL = 1;
    for (int i = 0; i < len - 1; i++){
        BL = (BL * B) % MOD;
    }
    //[0,len-1] 的 hash 值
    long h = 0;
    for (int i = 0; i < len; i++){
        h = (h * B + S.charAt(i) - 'a') % MOD;
    }
    //这里肯定不能直接存字符串做冲突检测，太大了会 MLE
    //存一个起始地址就可以了 len 已知
    HashMap<Long,Integer> map = new HashMap<>();
    map.put(h, 0);
    //rolling hash
    for (int i = 1; i <= S.length() - len; i++){
        //+MOD 是为了负数取模
        h = (h - (S.charAt(i-1) - 'a') * BL % MOD + MOD) % MOD;
        h = (h * B + (S.charAt(len + i -1) - 'a')) % MOD;
        Integer start = map.get(h);
        if (start != null && S.substring(start, start + len).equals(S.substring(i, i + len))){
            return i;
        }
        map.put(h, i);
    }
    return -1;
}

关于这个冲突检测有一个小问题，我尝试减小了MOD的大小，比如 101，这样计算出来的结果在数据量较大的就不对了，得到的字符虽然确实是重复了，但是并不是最长的，按道理写了冲突检测后即使我 MOD 取 1 应该都是可以找出来的啊？======> 在写上面这段话的时候突然想明白了，因为MOD取的太小，导致冲突的概率大大增加，而这里我做冲突检测的时候只保存了一个值，也就是说会有很多值被舍弃掉，也许你舍弃的值可能恰好就是最后的答案，字符越长，发生这种情况的概率就越高，所以说我这里冲突检测做的并不完全，能过也纯属运气，正确的冲突检测应该保存一个List链表，然后在发生冲突的时候在 List 中找有没有和当前字符相等的，这样一来，时间复杂度就会上去（其实这个过程就是设计 Hash 表的过程，链地址法解决冲突）

解法三

下面的应该就没什么问题了，链地址法，时间复杂度会增大，耗时增加到了 500ms+，但是确保了 100%的正确率，这是值得的，这次把 mod 调小也不会出错了（但是可能会 TLE，冲突变大了），总体来说，这几番折腾收获还是挺大的，好事还是要多磨啊

//再写一波检测冲突。
//上面的写的有问题，检测不完全
public String longestDupSubstring(String S) {
    int n = S.length();
    long MOD = (long) 1e9+7;
    int B = 26; 
    int left = 1;
    int right = n - 1;
    int start = -1, mlen = 0;
    while (left <= right){
        int mid = left + (right - left)/2;
        int temp = RabinKarp(mid, B, S, MOD);
        if (temp != -1){
            if (mid > mlen){
                mlen = mid;
                start = temp;
            }
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
    return start == -1 ? "" : S.substring(start, start + mlen);
}

public int RabinKarp(int len, int B, String S, long MOD){
    //hash(S) = s[0] * B^(len-1) + s[1] * B^(len-2) + ... + s[n-1] *1
    //B^(len-1) （移除左端点时需要的值）
    long BL = 1;
    for (int i = 0; i < len - 1; i++){
        BL = (BL * B) % MOD;
    }
    //[0,len-1] 的 hash 值
    long h = 0;
    for (int i = 0; i < len; i++){
        h = (h * B + S.charAt(i) - 'a') % MOD;
    }
    //这里肯定不能直接存字符串做冲突检测，太大了会 MLE
    //存一个起始地址就可以了 len 已知
    HashMap<Long,List<Integer>> map = new HashMap<>();
    map.put(h, new ArrayList(){{add(0);}});
    //rolling hash
    for (int i = 1; i <= S.length() - len; i++){
        //+MOD 是为了负数取模
        h = (h - (S.charAt(i-1) - 'a') * BL % MOD + MOD) % MOD;
        h = (h * B + (S.charAt(len + i -1) - 'a')) % MOD;
        List<Integer> starts = map.get(h);
        if (check(starts, i, S, len)){
            return i;
        }
        if (starts == null){
            List<Integer> lis = new ArrayList<>();
            lis.add(i);
            map.put(h, lis);
        }else{
            starts.add(i);
        }
    }
    return -1;
}

public boolean check(List<Integer> starts, int i, String s, int len){
    if(starts == null || starts.size() <= 0){
        return false;
    }
    for (int left : starts) {
        if(s.substring(left, left + len).equals(s.substring(i, i + len))){
            return true;
        }
    }
    return false;
}

718. 最长重复子数组

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例 1:

输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1]。

说明：

1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

解法一

dp 的解法是 O(N^2) 的，略显暴力，动态规划的解法放在 dp 专题中，这里要介绍的是二分+字符串 Hash 的O(NlogN)的解法

这里直接莽过了，且效率极高（16ms），就不写冲突检测了

public int findLength(int[] A, int[] B) {
    int lenA = A.length, lenB = B.length;
    int left = 1;
    int right = Math.min(lenA, lenB);
    int res = 0;
    while (left <= right){
        int mid = left +(right - left) / 2;
        if(RabinKarp(A, B, mid)){
            res = Math.max(res, mid);
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
    return res;
}

public boolean RabinKarp(int[] A,int[] B, int L){
    int MOD = (int) 1e9+7, BASE = 101;
    long BL = 1;
    for(int i = 0; i < L-1; i++){
        BL = (BL * BASE) % MOD;
    }
    //hash(A[0,L-1]),hash(B[0,L-1])
    long hA = 0, hB = 0;
    for(int i = 0; i < L; i++){
        hA = (hA * BASE + A[i]) % MOD;
        hB = (hB * BASE + B[i]) % MOD;
    }
    HashSet<Long> set =new HashSet<>();
    set.add(hA);
    //rolling hash A
    for(int i = 1; i <= A.length - L; i++){
        hA = (hA - A[i-1] * BL % MOD + MOD) % MOD;
        hA = (hA * BASE + A[L + i -1]) % MOD;
        set.add(hA);
    }
    if(set.contains(hB)) return true;
    //rolling hash B
    for(int i = 1; i <= B.length - L; i++){
        hB = (hB - B[i-1] * BL % MOD + MOD) % MOD;
        hB = (hB * BASE + B[L + i -1]) % MOD;
        //这里还可以做一下冲突检测，set 中需要多存一些信息
        if(set.contains(hB)){
            return true;
        }
    }
    return false;
}

哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子"I reset the computer. It still didn’t boot!"已经变成了"iresetthecomputeritstilldidntboot"。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。

注意： 本题相对原题稍作改动，只需返回未识别的字符数

示例：

输入：
dictionary = ["looked","just","like","her","brother"]
sentence = "jesslookedjustliketimherbrother"
输出： 7
解释： 断句后为"jess looked just like tim her brother"，共 7 个未识别字符。

提示：

0 <= len(sentence) <= 1000
dictionary中总字符数不超过 150000。
你可以认为dictionary和sentence中只包含小写字母。

解法一

动态规划和 Trie 的解法左转动态规划专题，这里记录下字符串 Hash 的做法，其实字符串 Hash 的做法相比字典树的做法会慢一点点，不过思路还是很值得学习的

这里看官方题解又学到了一点东西，这里在计算 hash 的时候加了一个 1，这样我猜测就是为了避免 0 的出现，使得后面的 base 失效，使得冲突的概率变大，比如aba和ba可能就会被判成一样的字符，我下面的做法没有做减a的操作，而是取了更大的 BASE，这里就不写冲突检测了，可以直接莽过，上面的第一题确实太离谱了，不按照官方题解的数据来就过不了

public int respace(String[] dictionary, String s) {
    int BASE = 131;
    long MOD = Integer.MAX_VALUE;
    HashSet<Long> set = new HashSet<>();
    for (String word : dictionary ) {
        set.add(hash(word, BASE, MOD));
    }
    int n = s.length();
    int[] dp = new int[n+1];
    for (int i = 1; i <=n ; i++) {
        dp[i] = dp[i-1] + 1;
        long rollhash = 0;
        for (int j = i; j >= 1; j--) {
            rollhash = (rollhash * BASE + s.charAt(j-1)) % MOD;
            if(set.contains(rollhash)){
                //注意这里是 dp[j-1]，对应 s.charAt(j-1) 的前一个字符
                dp[i] = Math.min(dp[i], dp[j-1]);
            }
            if(dp[i] == 0){
                break;
            }
        }
    }
    return dp[n];
}

//注意需要逆向 hash，上面计算的时候是 j--，是逆向的
public long hash(String s, int BASE, long MOD){
    long h = 0;
    for (int i = s.length()-1; i >=0 ; i--) {
        h = (h * BASE + s.charAt(i)) % MOD;
    }
    return h;
}

这个解法也用到了 Hash 表，但是相比用 Hash 表存字符，存数字的时间复杂度会低很多，其实字符串 Hash 也就是为了避免在 Hash 表中存大量的字符，一来空间占用会非常大，二来对于字符串来说计算字符的hashCode()的时间复杂度也是 O(N) 不可忽略的，而数字长度固定，hashCode()直接返回值就行了

1316. 不同的循环子字符串

Difficulty: 困难

给你一个字符串 text ，请你返回满足下述条件的不同非空子字符串的数目：

可以写成某个字符串与其自身相连接的形式（即，可以写为 a + a，其中 a 是某个字符串）。

例如，abcabc 就是 abc 和它自身连接形成的。

示例 1：

输入：text = "abcabcabc"
输出：3
解释：3 个子字符串分别为 "abcabc"，"bcabca" 和 "cabcab" 。

示例 2：

输入：text = "leetcodeleetcode"
输出：2
解释：2 个子字符串为 "ee" 和 "leetcodeleetcode" 。

提示：

1 <= text.length <= 2000
text 只包含小写英文字母。

解法一

哭了，看着 KMP 的 tag 进来的，结果发现 KMP 的不太会写，学习了题解的前缀和 Hash 的思路，还是有点收获

int BASE = 131;

long MOD = (long)1e9+7;

public int distinctEchoSubstrings(String s) {
    int n = s.length();
    //前缀 hash 和（前 i 个元素的 hash 值）
    long[] hashSum = new long[n+1];
    //BASE 的所有幂乘
    long[] pow = new long[n+1];
    pow[0] = 1;
    hashSum[0] = 0;
    for (int i = 1; i <= n; i++) {
        hashSum[i] = (hashSum[i-1]*BASE + s.charAt(i-1)) % MOD;
        pow[i] = (pow[i-1]*BASE) % MOD;
    }
    HashSet<Long> set = new HashSet<>();
    //枚举所有偶数长度的子串
    for (int len = 2; len <= n; len+=2) {
        for (int i = 0 ; i+len-1 < n; i++) {
            int j = i + len - 1; //右边界
            int mid = i + (j-i)/2; //中点
            //0,3
            long hleft = getHash(hashSum, pow, s, i, mid);
            long hright = getHash(hashSum, pow, s, mid+1, j);
            if(hleft == hright && !set.contains(hleft)){
                set.add(hleft);
            }
        }
    }
    return set.size();
}

// 求 s[i,j] 区间的哈希值：s[i]*B^j-i + s[i+1]*B^j-i-1 + ... + s[j]
// 
// hashSum[i] = s[0]*B^i-1 + s[1]*B^i-2 +...+ s[i-1]
// hashSum[j+1] = s[0]*B^j + s[1]*B^j-1 +...+ s[j]
// hashSum[i]*B^j-i+1 = s[0]*B^j + s[1]*B^j-1 +...+ s[i-1]*B^j-i+1
// hash[i,j] = hashSum[j+1] - hashSum[i] * B^j-i+1
//           = s[i]*B^j-i + s[i+1]*B^j-i-1 +...+s[j]
public long getHash(long[] hashSum, long[] pow, String s, int i, int j){
    //j-i+1 是 [i,j] 区间的长度，包含 i 和 j，而 hashSum[k] 是不包含 k 的
    //所以这里需要转换下，j 需要+1 使得 hashSum 包含 j
    return (hashSum[j+1] - (hashSum[i] * pow[j-i+1]) % MOD + MOD) % MOD;
}

解法二

KMP 的做法肯定就是参考 KMP 的 459. 重复的子字符串的做法，我看了外网的 discuss，只看见了一个这样写的，而且看不太懂，我自己尝试了下，感觉好多地方都会有坑，主要就是去重很麻烦，代码如下

下面为错误解法，无法通过 OJ，懒得改了，感觉不是个很好的做法

//KMP 的做法
public int distinctEchoSubstrings(String s) {
    for (int i = 0; i < s.length(); i++) {
        getNext(s.substring(i));
    }
    return set.size();
}

HashSet<String> set = new HashSet<>();

public void getNext(String s){
    if(s.length() < 2){
        return;
    }
    int n = s.length();
    int[] next = new int[n+1];
    next[0] = -1;
    next[1] = 0;
    int left = 0, right = 2;
    while(right <= n){
        if(s.charAt(left) == s.charAt(right-1)){
            left++;
            next[right] = left;
            int replen = right-next[right];
            String rs = s.substring(0,replen);
            if (right%2==0 && replen!=right && right%replen==0 && !set.contains(rs)) {
                set.add(rs);
            }
            right++;
        }else if(next[left] == -1){
            right++;
        }else{
            left = next[left];
        }
    }
}

目录

Rabin-Karp 算法

1044. 最长重复子串

718. 最长重复子数组

面试题 17.13. 恢复空格

1316. 不同的循环子字符串