Задача: 1044. Longest Duplicate Substring
Сложность: hard

Учитывая строку s, рассмотрите все дублированные подстроки: (смежные) подстроки s, которые встречаются 2 или более раз.Вхождения могут перекрываться. Верните любую дублированную подстроку, которая имеет наибольшую возможную длину.Если в s нет дублирующейся подстроки, ответом будет "".

Пример:

Input: s = "banana"
Output: "ana"

👨‍💻 Алгоритм:

1⃣Использование двоичного поиска для определения длины дублированной подстроки:
Двоичный поиск используется для поиска максимальной длины дублированной подстроки.

2⃣Использование хеширования для проверки наличия дублированной подстроки определенной длины:
Для каждой длины, определенной двоичным поиском, используем хеширование для поиска подстрок.

3⃣Хеширование с помощью функции rolling hash:
Rolling hash позволяет быстро вычислять хеши подстрок фиксированной длины и сравнивать их для поиска дубликатов.

😎 Решение:

function longestDupSubstring($s) {
    function search($s, $length) {
        $seen = [];
        for ($i = 0; $i <= strlen($s) - $length; $i++) {
            $sub = substr($s, $i, $length);
            if (isset($seen[$sub])) {
                return $sub;
            }
            $seen[$sub] = true;
        }
        return "";
    }

    $left = 1;
    $right = strlen($s);
    $result = "";
    while ($left < $right) {
        $mid = intdiv($left + $right, 2);
        $dup = search($s, $mid);
        if ($dup !== "") {
            $result = $dup;
            $left = $mid + 1;
        } else {
            $right = $mid;
        }
    }
    return $result;
}

Ставь 👍 и забирай 📚 Базу знаний