1044. 最长重复子串 编程语言:java、python

最长重复子串
给你一个字符串 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大神们的思路,结合自己的理解给大家注解,如果有任何问题与疑问,欢迎指出来!
注解完毕,以上代码过于复杂,但是想明白会感觉神清气爽!
至此最长子串讲解完毕!!!

上一篇:MYSQL 数据库索引类型简介


下一篇:【Airtest】使用Airtest进行iOS自动化测试