最长重复子串
给你一个字符串 s ,考虑其所有 重复子串 :即,s 的连续子串,在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。
返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串,那么答案为 “” 。
输入:s = “banana”
输出:“ana”
输入:s = “banana”
输出:“ana”
今天针对这道题目,我给出相应的代码解析,刚开始的我采用的是
Java编码,主要是利用确定一个左边界,然后利用右边界平移来判断String字符串中是否有重复子串出现,
提到重复子串其实本质上就是判断是否在该子串外还存在该子串。
class Solution {
public String longestDupSubstring(String s) {
String result="";
int i=0;
int j=1;
int length=0;
int n=s.length();
while(i<n)
{
if(s.substring(i+1).contains(s.substring(i,j)))//这个是判断是否有重复子串
{
if(length<j-i)
{
length=j-i;
result=s.substring(i,j);
}
j++;
i--;//后退一步
}
i++;//前进一步,所以i不变
}
但是很不幸的消息告诉你们,最大的错误不是错误,而是超时!!!
因为我用了substring方法以及contains方法,哎,难怪是难题,实在是高!
接下来我采用我的第二语言python编程:
class Solution:
def longestDupSubstring(self, s: str) -> str:
result = ''
j = 1
while i < len(s):
if s[i: j] in s and s[i: j] in s[i + 1:]:
if max_len < j - i:
result = s[i: j]
j += 1
i -= 1
i += 1
return result
用这个方法是硬生生把跑出来了,当然python的切片比Java的切片性能要好点呀!
然后重头戏来了,那么用Java怎么较好地实现呢?
那么就是采用二分降低时间复杂度+字符串hash(字符串查找始终没有数字快),因此就采用这种方法把
字符串hash可以通俗理解为,把一个字符串转换为一个整数。
但是要防止一点就是不要出现hash冲突,这点能保证其为单向映射。
简化公式:hash[i]=hash[i-1]*p+idx(s[i]),p为质数
class Solution {
private static final int P=1313131;//定义质数P,防止出现hash冲突
long[] h,p;
public String longestDupSubstring(String s) {
int n=s.length();.//得到字符串的长度
//这下面是为了hash运算准备hash数组以及次方数组
h=new long[n+1];//定义long类型的数组,这里加1的目的是因为h[i+1]的赋值操作
p=new long[n+1];//与上同
p[0]=1;//定义第二个数组首位置为1,也就是次方数组,目的是让它与数组长度无关,也就是长度为1一次方,长度为2位2次方....
for(int i=0;i<n;i++){
h[i+1]=h[i]*P+s.charAt(i);//初始化hash值
p[i+1]=p[i]*P;//初始化p数组
}
String result="";//初始化返回函数
int left=0,right=n;//初始化左右边界
while(left<right){
int mid=(left+right)/2; //二分法子串大小
String a=checked(s,mid); //判断是否存在重复子串
if(a.length()>0){
left=mid+1; //找到大于0说明存在,存在就继续进一步搜索,这里的目的是扩大搜索范围,每次增加的都是mid/2指标
result=result.length()<mid?a:result;
}
else right=mid;//找不到说明只能把返回卡死在mid中,也就是0-mid
}
return result;//输出结果
}
private String checked(String s,int d){
Set<Long> set=new HashSet<>();//无序不重复,记住哦
for(int i=0;i+d<=s.length();i++){
long hash=h[i+d]-h[i]*p[d]; //获取子串的hash值
if(set.contains(hash))return s.substring(i,i+d);//如果存在就返回
else set.add(hash);//不存在就添加hash值
}
return "";//没有就返回空串
}
}
注明:部分代码参考了LeetCode大神们的思路,结合自己的理解给大家注解,如果有任何问题与疑问,欢迎指出来!
注解完毕,以上代码过于复杂,但是想明白会感觉神清气爽!
至此最长子串讲解完毕!!!