最长重复子串Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

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

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

示例 1：

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

示例 2：

输入：s = "abcd"
输出：""

提示：

2 <= s.length <= 3 * 10⁴
s 由小写英文字母组成

# 思路

但是这种方式每次都要substring，但是hash碰撞太高，所以要进行改进

# 解法

class Solution {

    public String longestDupSubstring(String s) {
        int first = 0;
        int last = s.length();
        while(first < last){
            int mid = (last - first) / 2 + first;
            int index = check(s, mid);
            if(index==-1){
                last = mid;
            }else{
                first = mid+1;
            }
        }
        //这里就找出了重复的长度
        int index = check(s, first-1);
        return s.substring(index,index+first-1);
    }

    //给一个字符串和一个长度，返回重复长度的下标index,没有返回-1
    //但是这种方式每次都要substring，但是hash碰撞太高，所以要进行改进
    public int check1(String s, int len){
        if(len==0){
            return 0;
        }
        Map<String,Integer> map = new HashMap<>();
        for(int i=0;i<=s.length()-len;i++){
            String str = s.substring(i,i+len);
            if(map.containsKey(str)){
                int index = map.get(str);
                return index;
            }
            map.put(str,i);
        }
        return -1;
    }

    private static int mod = 1000000007;

    //这里需要使用Rabin-Karp算法来解决len长度的字符串在s中是否重复，也就是使用hash的方式
    public int check(String s, int len){
        if(len==0){
            return 0;
        }
        long pow = 1;
        for(int i=0;i<len;i++){
            pow = (pow*31)%mod;
        }
        //再来计算hash值
        long hash =0;
        Map<Long,Integer> map = new HashMap<>();
        for(int i=0;i<s.length();i++){
            hash = (hash*31+(s.charAt(i)-'a'))%mod;
            if(i<len-1){
                //这时候还不满足，继续
                continue;
            }
            if(i>=len){
                //这时候就要把前面的字符去掉
                hash-=((s.charAt(i-len)-'a')*pow)%mod;
                hash+=hash<0?mod:0;
            }
            if(map.containsKey(hash)){
                //说明这个hash之前出现过
                int index = map.get(hash);
                String str1 = s.substring(index,index+len);
                String str2 = s.substring(i+1-len,i+1);
                if(str1.equals(str2)){
                    return index;
                }
            }
            map.put(hash,i-len+1);
        }
        return -1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

# 总结

分析出几种情况，然后分别对各个情况实现

#Java