Блог

Я решал Leetcode 1044, и ответ заключается в использовании двоичного поиска и скользящего хэша. В основном используйте двоичный поиск, чтобы выбрать длину, а затем выполнить поиск дублирующейся строки этой длины. Здесь для экономии места используется скользящий хэш (вместо использования набора для хранения всей подстроки мы храним хэш подстроки). Это основа для решения.

Мой вопрос касается модуля, используемого для предотвращения переполнения. Я выбрал Long.MAX_VALUE, который, как я считаю, достаточно большой, чтобы справиться с этим, но ответ неверен, когда я использую Long.MAX_VALUE. Однако, когда я использую Long.MAX_VALUE / 26 или Math.pow(2, 32), они оба работают. Извините, я довольно плохо разбираюсь в модуле, и я думаю, что я определенно пропустил здесь некоторые вещи. Кто-нибудь может пролить свет на это? Спасибо! Мое решение заключается в следующем:

 public static long modulus = Long.MAX_VALUE / 26;
public String longestDupSubstring(String S) {
    int n = S.length();
    int l = 1;
    int r = n - 1;
    int index = -1;
    while (l <= r) {
        int m = l   (r - l) / 2;
        int temp = findDuplicate(S, m);
        if (temp != -1) {
            index = temp;
            l = m   1;
        }
        else {
            r = m - 1;
        }
    }
    return index == -1 ? "" : S.substring(index, index   r);
}
private int findDuplicate(String s, int len) {
    Set<Long> set = new HashSet<>();
    long hash = 0;
    long p = 1;
    for (int i = 0; i < len; i  ) {
        hash = (hash * 26   s.charAt(i) - 'a') % modulus;
        p = (p * 26) % modulus;
    }
    set.add(hash);
    
    for (int i = len; i < s.length(); i  ) {
        hash = (hash * 26   (s.charAt(i) - 'a')
                - (s.charAt(i - len) - 'a') * p) % modulus;
        if (hash < 0) {
            hash  = modulus;
        }
        if (set.contains(hash)) {
            return i - len   1;
        }
        set.add(hash);
    }
    return -1;
}
  

26 не является частью модуля, является частью хеширования. Если бы мы разделили их в алгоритме, тогда мы могли бы увидеть, как это будет работать. Для модуля обычно достаточно большого числа, не обязательно должно быть long :

 public final class Solution {
    int a = 26;
    int mod = 1 << 29;

    public final String longestDupSubstring(
        final String s
    ) {
        int lo = 1;
        int hi = s.length() - 1;

        while (lo <= hi) {
            int mid = lo   ((hi - lo) >> 1);
            int startIndex = search(s, mid);

            if (startIndex == - 1) {
                hi = mid - 1;
            }

            else {
                lo = -~mid;
            }
        }

        int startIndex = search(s, hi);
        return startIndex == -1 ? "" : s.substring(startIndex, startIndex   hi);
    }

    public final int search(
        final String s,
        final int len
    ) {
        long h = 0;
        long aL = 1;

        for (int i = 0; i < len; i  ) {
            h = (h * a % mod   s.charAt(i)) % mod;
            aL = aL * a % mod;
        }

        HashMap<Long, List<Integer>> visited = new HashMap<>();
        visited.put(h, new ArrayList<Integer>());
        visited.get(h).add(0);

        for (int i = 1; i < -~s.length() - len; i  ) {
            h = ((h * a % mod - s.charAt(i - 1) * aL % mod   mod) % mod   s.charAt(i   len - 1)) % mod;

            if (visited.containsKey(h)) {
                for (int start : visited.get(h)) {
                    if (s.substring(start, start   len).equals(s.substring(i, i   len))) {
                        return i;
                    }
                }

            } else {
                visited.put(h, new ArrayList<Integer>());
            }

            visited.get(h).add(i);
        }

        return -1;
    }
}