字符串编码Rabin-Karp算法Leetcode 1044. 最长重复子串
2021/12/24 1:07:29
本文主要是介绍字符串编码Rabin-Karp算法Leetcode 1044. 最长重复子串,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
最长重复子串
注意的点:
- 字符串是全部小写字母,所以其实就是26进制,这里去比26大的最小质数
- C++中unsigned long long会自动处理上溢(相乘、相加超出了它能表示的最大范围2^64-1)和下溢(因为减法使得小于0)
- 求多少次方的时候,可以使用快速幂
class Solution { public: int n; unsigned long long a=29; unsigned long long my_power(int m){ unsigned long long ans=1; unsigned long long k=a; while(m!=0){ if(m%2==1) ans=ans*k; k=k*k; m=m/2; } return ans; } int check_s(vector<int> &val,int len){ unsigned long long sum=0,cur; for(int i=0;i<len;i++){ sum=a*sum+(unsigned long long)val[i]; } cur=my_power(len); unordered_set<unsigned long long> st; st.insert(sum); for(int i=1;i<=n-len;i++){ sum=sum*a-(unsigned long long )val[i-1]*cur+(unsigned long long )val[i+len-1]; if(st.count(sum)) return i; else st.insert(sum); } return -1; } string longestDupSubstring(string s) { n=s.size(); vector<int> val(n); for(int i=0;i<n;i++) val[i]=s[i]-'a'; int l=1,r=n-1; int k=-1,len; while (l<=r){ int mid=(l+r)>>1; int start= check_s(val,mid); if(start!=-1){ k=start; len=mid; l=mid+1; }else r=mid-1; } if(k==-1) return ""; else return s.substr(k,len); } };
这篇关于字符串编码Rabin-Karp算法Leetcode 1044. 最长重复子串的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享