Задача: 1062. Longest Repeating Substring
Сложность: medium

Дана строка s. Вернуть длину самой длинной повторяющейся подстроки. Если повторяющаяся подстрока отсутствует, вернуть 0.

Пример:

Input: s = "abcd"
Output: 0
Explanation: There is no repeating substring.

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

1⃣Перемещайте скользящее окно длиной L по строке длиной N.

2⃣Проверьте, находится ли строка в скользящем окне в хэш-наборе уже виденных строк. Если да, то повторяющаяся подстрока находится здесь. Если нет, сохраните строку из скользящего окна в хэш-наборе.

3⃣Очевидный недостаток этого подхода — большое потребление памяти в случае длинных строк.

😎 Решение:

class Solution {
    function search($L, $n, $S) {
        $seen = [];
        for ($start = 0; $start <= $n - $L; ++$start) {
            $tmp = substr($S, $start, $L);
            if (in_array($tmp, $seen)) return $start;
            $seen[] = $tmp;
        }
        return -1;
    }

    function longestRepeatingSubstring($S) {
        $n = strlen($S);
        $left = 1; $right = $n;
        while ($left <= $right) {
            $L = $left + intdiv($right - $left, 2);
            if ($this->search($L, $n, $S) !== -1) {
                $left = $L + 1;
            } else {
                $right = $L - 1;
            }
        }
        return $left - 1;
    }
}

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