最长重复子串
给你一个字符串 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
但是很不幸的消息告诉你们，最大的错误不是错误，而是超时！！！
因为我用了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^d+idx(s[i])，p为质数,d为长度次方根
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;i0){
left=mid+1; //找到大于0说明存在，存在就继续进一步搜索，这里的目的是扩大搜索范围
result=result.length() 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大神们的思路，结合自己的理解给大家注解，如果有任何问题与疑问，欢迎指出来！
注解完毕，以上代码过于复杂，但是想明白会感觉神清气爽！
至此最长子串讲解完毕！！！
