Задача с собеседования в

Задача с собеседования в eBay Дана строка s, проверьте, можно ли составить её, взяв какую-либо её подстроку и повторив её два или более раз подряд. Пример 1: Input: s = "abab" Output: true Explanation: Это подстрока "ab", повторяющаяся дважды. Пример 2: Input: s = "aba" Output: false Пример 3: Input: s = "abcabcabcabc" Output: true Explanation: Это подстрока "abc", повторяющаяся четыре раза, или подстрока "abcabc", повторяющаяся дважды. Ограничения: 1 <= s.length <= 10⁴ s состоит из строчных английских букв. НАШ ЧАТ АЛГОРИТМИСТОВ Решение Если s состоит из повторяющихся подстрок, то у неё есть длинный собственный префикс, равный её суффиксу. Классический метод решения задачи - префикс-функция из алгоритма Кнута-Морриса-Пратта . Префикс-функция даёт длины наибольших бордеров для всех префиксов. Бордер - собственный префикс строки, являющийся одновременно её суффиксом. Необходимо проверить, образует ли бордер период всей строки. Создаем массив lps (longest prefix-suffix), где lps[i] хранит длину наибольшего собственного префикса подстроки s[0..i], который одновременно является её суффиксом. Если при вычислении префикс-функции символы не совпадают, длина префикса (k) не сбрасывается в ноль, а "откатывается" к уже вычисленному значению для более короткого префикса. Идём по строке слева направо, храня k - длину текущего совпавшего префикса: Пока k > 0 (префикс непустой) и s[i] != s[k] (символы не совпали): - "откатываемся" к наибольшему валидному бордеру меньшей длины: k = lps[k - 1] (если префикс s[0..k-1] равен суффиксу s[i-k..i-1], то любой бордер строки s[0..k-1] также является бордером и для s[0..i-1]. Наибольший такой бордер имеет длину lps[k - 1]). Если s[i] == s[k]: - продлеваем совпавший префикс текущим символом (k += 1). Записываем результат: lps[i] = k. Разберем на примере 1, где s = "abab": - Подстрока "a" (i = 0): собственных префиксов нет => lps[0] = 0. - Подстрока "ab" (i = 1): префикс "a" != суффикс "b" => lps[1] = 0. - Подстрока "aba" (i = 2): префикс "a" == суффикс "a" => lps[2] = 1. - Подстрока "abab" (i = 3): префикс "ab" == суффикс "ab" => lps[3] = 2. Получившийся массив lps: [0, 0, 1, 2] L (длина бордера всей строки) = lps[n - 1]. Если L > 0, то префикс длины L совпадает с суффиксом длины L: s[0..L-1] == s[n-L..n-1]. Суффикс начинается с индекса n - L, т.е. для любого индекса j от 0 до L-1 будет выполняться s[j] == s[j + (n - L)]. Таким образом, строка сдвигается сама на себя с шагом p = n - L. p - кандидат на длину минимального периода. Чтобы строка состояла из точных повторов этого периода, должны выполняться следующие два условия: - L > 0 (иначе p = n и n % n == 0 даст true для любой строки, к примеру, "abcd") - n % p == 0 (общая длина строки должна нацело делиться на длину периода. К примеру, для "ababa", где n = 5, L = 3, p = 2 и 5 % 2 != 0). Сложность O(n) - по времени (k увеличивается не более чем на 1 за каждую итерацию внешнего цикла for, в цикле while - k только уменьшается. Таким образом, суммарное число итераций while не превышает n) O(n) - по памяти (строим массив lps) Код class Solution: def repeatedSubstringPattern(self, s: str) -> bool: n = len(s) lps = [0] * n for i in range(1, n): k = lps[i - 1] while k > 0 and s[i] != s[k]: k = lps[k - 1] if s[i] == s[k]: k += 1 lps[i] = k L = lps[n - 1] p = n - L return L > 0 and n % p == 0 @algoses