leetcode-1044:最长重复子串(滚动哈希)

简介: leetcode-1044:最长重复子串(滚动哈希)

题目

题目链接

给你一个字符串 s ,考虑其所有 重复子串 :即,s 的连续子串,在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。

返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串,那么答案为 “” 。

示例 1:

输入:s = "banana"
输出:"ana"

示例 2:

输入:s = "abcd"
输出:""

解题

方法一:Rabin-Karp(滚动哈希) + 二分搜索

参考链接

最后利用二分查找选择长度,因为如果长度小的子字符串sub1存在,那么它可能是长度大的子字符串sub2的子字符串

如果长度大的子字符串不存在重复,那么更大的子字符串也不可能重复。

class Solution {
public:
    uint64_t prime=31;
    string longestDupSubstring(string s) {
        int n=s.size();
    //滚动哈希,查找指定长度的字符串
        auto find=[&](int len){
            uint64_t hash=0;
            uint64_t power=1;
      //初始化哈希
            for(int i=0;i<len;i++){
                hash=hash*prime+s[i]-'a';
                power*=prime;
            }
            //查找哈希是否之前遇到过
            unordered_set<uint64_t> set{hash};
            for(int i=len;i<n;i++){
                hash=hash*prime-power*(s[i-len]-'a')+s[i]-'a';
                if(set.count(hash)) return i-len+1;
                set.insert(hash);
            }
            return -1;
        };
    //二分查找(选则长度)
        int l=0;
        int r=n-1;
        int pos=-1;
        int len=0;
        while(l<=r){
            int mid=(l+r)/2;
            int start=find(mid);
            if(start!=-1){
                len=mid;
                pos=start;
                l=mid+1;
            }
            else{
                r=mid-1;
            }
        }
        if(pos==-1) return "";
        return s.substr(pos,len);
    }
};

补充:

unsigned long long 是可以自动取余的,因此不会出现超过上界。为了防止哈希冲突,一般prime选择素数,然后需要更具测试集去选定。


相关文章
|
2月前
《LeetCode》—— 哈希
《LeetCode》—— 哈希
|
1月前
|
算法 数据挖掘 开发者
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
|
1月前
|
存储 SQL 算法
LeetCode 题目 87:递归\动态规划\哈希实现 扰乱字符串
LeetCode 题目 87:递归\动态规划\哈希实现 扰乱字符串
|
2月前
[leetcode] 705. 设计哈希集合
[leetcode] 705. 设计哈希集合
|
2月前
leetcode-1001:网格照明(自定义哈希集合)
leetcode-1001:网格照明(自定义哈希集合)
25 0
|
算法 索引
leetcode-每日一题745. 前缀和后缀搜索(哈希和字典树)
如果我们用前缀 prefix 和 后缀 suff去暴力对比所有单词肯定会超时,我们可以先把单词里所有的前缀后缀组合,中间用特殊符号@连接,对应的最大下标存入哈希表中。搜索时,用特殊符号@连接前缀后缀,在哈希表中进行搜索
71 0
leetcode-每日一题745. 前缀和后缀搜索(哈希和字典树)
|
算法
leetcode-每日一题873. 最长的斐波那契子序列的长度(哈希和二分)
题目要求斐波那契数列长度要大于等于3,就等于说要确定 x[1] 和 x[2]来确定x[3]…x[n]之和的数列,所以我们用两层for循环来枚举x[1] 和 x[2] ,因为斐波那契数列满足 x[i] = x[i - 1] + x[i - 2], 所以x[3] = x[1] + x[2] x[4] = x[3] + x[2]…,我们只需要三个变量来不断变换, 每次从 arr 中找前两个数,然后查看后续在符合斐波那契的数在arr中是否存在
87 0
leetcode-每日一题873. 最长的斐波那契子序列的长度(哈希和二分)
|
算法
leetcode-每日一题648. 单词替换(哈希)
将字符串数组中的所有字符串存入哈希表中,遍历sentence中的所有单词,从短到长遍历单词前缀,对比哈希表中的单词是否存在,存在则替换。
57 0
leetcode-每日一题648. 单词替换(哈希)
|
算法 容器
力扣17 - 电话号码的字母组合【回溯、哈希映射、队列】
对应力扣.17电话号码的字母组合,详细动画和图示讲解,带你快乐刷题
59 0
力扣17 - 电话号码的字母组合【回溯、哈希映射、队列】
|
算法 C语言 容器
力扣260 - 只出现一次的数字||| 【哈希映射、异或位运算+分治思想】
对应力扣260.只出现一次的数字|||,包含哈希映射和异或位运算+分治思想两种解法,超详细步骤讲解
129 0
力扣260 - 只出现一次的数字||| 【哈希映射、异或位运算+分治思想】