欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JAVA程序设计:最长重复子串(LeetCode:1044)

程序员文章站 2023-12-29 14:21:34
给出一个字符串S,考虑其所有重复子串(S 的连续子串,出现两次或多次,可能会有重叠)。返回任何具有最长可能长度的重复子串。(如果 S不含重复子串,那么答案为""。)示例 1:输入:"banana"输出:"ana"示例 2:输入:"abcd"输出:""提示:2 <= S.length <= 10^5S 由小写英文字母组成。思路:二分长度+哈希,通过二分长度我们可以每次根据固定长度判断是否存在重复子串,而在找重复子串的过程中我们需要进一步优化,通过......

给出一个字符串 S,考虑其所有重复子串(S 的连续子串,出现两次或多次,可能会有重叠)。

返回任何具有最长可能长度的重复子串。(如果 S 不含重复子串,那么答案为 ""。)

 

示例 1:

输入:"banana"
输出:"ana"
示例 2:

输入:"abcd"
输出:""
 

提示:

2 <= S.length <= 10^5
S 由小写英文字母组成。

思路:二分长度+哈希,通过二分长度我们可以每次根据固定长度判断是否存在重复子串,而在找重复子串的过程中我们需要进一步优化,通过哈希的方法快速找到当前长度的串是否含有子串。

有一个问题是,为啥我余数用Integer.MAX.VALUE反而会造成哈希冲突?

class Solution {

    private String ans;
    static final long P = (long)(Math.pow(2,32));
    static final long BASE = 26;

    public String longestDupSubstring(String S) {

        ans = "";
        int l = 1, r = S.length();
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(mid, S))
                l = mid + 1;
            else
                r = mid - 1;
        }

        return ans;
    }

    private boolean check(int x, String s) {

        int len = s.length();
        Set<Long> st = new HashSet<>();
        long[] hashValue = new long[len];

        hashValue[0] = s.charAt(0) - 'a';
        for (int i = 1; i < x; i++)
            hashValue[i] = (hashValue[i - 1] * BASE + (s.charAt(i) - 'a')) % P;
        st.add(hashValue[x - 1]);
        for (int i = x; i < len; i++) {
            hashValue[i] = (hashValue[i - 1] * BASE + (s.charAt(i) - 'a')) % P;
            long val = (hashValue[i] - hashValue[i - x] * q(BASE, x) % P + P) % P;
            if (st.contains(val)) {
                ans = s.substring(i - x + 1, i + 1);
                return true;
            }
            st.add(val);
        }

        return false;
    }

    private long q(long x, long y) {
        long res = 1;
        while (y > 0) {
            if (y % 2 == 1)
                res = res * x % P;
            x = x * x % P;
            y /= 2;
        }
        return res;
    }

}

 

本文地址:https://blog.csdn.net/haut_ykc/article/details/107248926

上一篇:

下一篇: