459. Repeated Substring Pattern

Задача

Дана строка s , проверьте, можно ли её составить, взяв подстроку из неё и соединив вместе несколько копий этой подстроки.

Примеры

Пример 1

Input: s = "abab"
Output: true

Пояснение

Это подстрока “ab”, повторённая дважды.

Пример 2

Input: s = "aba"
Output: false

Пример 3

Input: s = "abcabcabcabc"
Output: true

Пояснение

Это “abc”, повторённая четыре раза, или “abcabc” дважды.

Решение

Решение

/**
 * Это «трюк», основанный на математическом свойстве периодических строк. 
 * Если строка S состоит из повторяющихся подстрок, 
 * то она обязательно найдется внутри строки 2*S (если отбросить первый и последний символы 2*S).
 * 
 * Временная сложность: O(N) — поиск подстроки
 * Пространственная сложность: O(N) — создание строки s + s
 */
var repeatedSubstringPattern = function(s) {
    // 1. Удваиваем строку: "abab" -> "abababab"
    // 2. Убираем первый и последний символы: "bababa"
    // 3. Ищем исходную "abab" внутри "bababa".
    // Если нашли — значит паттерн есть.
    return (s + s).slice(1, -1).includes(s);
};

Решение 2

/**
 * Временная сложность: O(N * √N) — в худшем случае, но обычно быстрее
 * Пространственная сложность: O(N) — для создания временных строк в repeat
 */
var repeatedSubstringPattern = function(s) {
    const n = s.length;
 
    // Идем от половины длины вниз
    for (let i = Math.floor(n / 2); i >= 1; i--) {
        // Ключевая оптимизация: проверяем только если длина делится на i без остатка
        if (n % i === 0) {
            const pattern = s.slice(0, i);
            const repeats = n / i;
 
            if (pattern.repeat(repeats) === s) {
                return true;
            }
        }
    }
 
    return false;
};

Решение 3 (Алгоритм Кнута-Морриса-Пратта (KMP))

/**
 * Временная сложность: O(N) — строгий линейный проход
 * Пространственная сложность: O(N) — массив lps
 */
var repeatedSubstringPattern = function(s) {
    const n = s.length;
    const lps = new Array(n).fill(0);
    let len = 0; // длина предыдущего наибольшего префикса-суффикса
    let i = 1;
 
    // Строим массив LPS
    while (i < n) {
        if (s[i] === s[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len > 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
 
    // Длина наименьшей повторяющейся подстроки
    const patternLen = n - lps[n - 1];
 
    // 1. lps[n-1] > 0: значит есть совпадающие префикс и суффикс
    // 2. n % patternLen === 0: длина строки делится на длину паттерна
    return lps[n - 1] > 0 && n % patternLen === 0;
};