Как оптимизировать алгоритм поиска уникальных сдвигов в данных?

Код работает, но алгоритм выглядит слишком сложным. Можно ли реализовать это проще или иным способом? <br/> <a href="https://jsbin.com/qezawoviho/edit?js" rel="nofollow">https://jsbin.com/qezawoviho/edit?js</a>
  • 31 марта 2026 г. 18:00
Ответы на вопрос 1
Я не могу открыть ваш jsbin, но по описанию — «поиск уникальных сдвигов в данных» — обычно имеют в виду циклические сдвиги (rotations) строки/массива и надо либо
- получить список всех различных циклических сдвигов, либо
- вернуть их количество.

Ниже кратко — три распространённых, простых и эффективных подхода с примерами на JavaScript. Выберите тот, который больше подходит под вашу задачу.

1) Очень простой (читабельный) — собирать сдвиги в Set
- Преимущество: очень простой код.
- Недостаток: строит n строк/массивов длины n — O(n^2) по времени и памяти, но для небольших n это нормально.

Пример (работает и для строки, и для массива чисел):
```js
// input: s — строка или массив
function uniqueRotationsSimple(s) {
  const n = s.length;
  const doubled = Array.isArray(s) ? s.concat(s) : s + s;
  const seen = new Set();

  for (let i = 0; i < n; i++) {
    const rot = Array.isArray(s)
      ? JSON.stringify(doubled.slice(i, i + n))   // для массива — stringify
      : doubled.slice(i, i + n);                  // для строки — substring
    seen.add(rot);
  }

  // вернуть массив уникальных сдвигов
  if (Array.isArray(s)) {
    return [...seen].map(x => JSON.parse(x));
  } else {
    return [...seen];
  }
}
```

2) Если нужно только количество уникальных сдвигов — использовать KMP (префикс-функцию) для нахождения минимального периода
- Очень быстрый: O(n).
- Правило: если строка/массив имеет минимальный период p (s = t^(n/p)), то число различных циклических сдвигов равно p. (Пример: "abab" -> p=2 -> только 2 различных сдвига.)
- Это самый простой и эффективный способ, если вам нужен именно счёт.

Пример:
```js
// возвращает минимальную длину периода (и, следовательно, число уникальных сдвигов)
function minimalPeriod(arr, eq = (a,b) => a === b) {
  const n = arr.length;
  const pi = new Array(n).fill(0);
  for (let i = 1; i < n; i++) {
    let j = pi[i - 1];
    while (j > 0 && !eq(arr[i], arr[j])) j = pi[j - 1];
    if (eq(arr[i], arr[j])) j++;
    pi[i] = j;
  }
  const k = n - pi[n - 1];
  return (n % k === 0) ? k : n;
}

// Использование:
// для строки: minimalPeriod("abab".split("")) -> 2
// для массива чисел: minimalPeriod([1,2,1,2], (a,b)=>a===b) -> 2
```

Если нужен не только счёт, но сами уникальные сдвиги — достаточно сгенерировать первые p сдвигов из doubled массива (где p = minimalPeriod).

3) Если вход большой и вы хотите высокую скорость и низкую аллокацию, можно использовать Rolling Hash (Rabin-Karp)
- Позволяет сравнивать сдвиги по хэшу O(1) после O(n) предвычисления.
- Остерегайтесь коллизий — используйте двойной хеш или большой модуль.
- Сложнее в реализации, но эффективнее по памяти/скорости по сравнению с хранением всех строк.

Небольшой набросок идеи:
- Конкатенировать s+s (для циклических подстрок).
- Построить префиксные хеши и степени базиса.
- Для каждого i вычислять хеш подстроки длины n и класть в Set.

Выбор:
- Для простоты и читаемости: Set (вариант 1).
- Для подсчёта уникальных сдвигов очень быстро и аккуратно: KMP / минимальный период (вариант 2).
- Для больших входов и строгих ограничений по памяти/скорости: Rolling Hash (вариант 3).

Если хотите — пришлите ваш код или объясните формат данных (строка/массив чисел, ожидаемый размер). Тогда я покажу точную переработку вашего варианта (например, заменить сложную логики на KMP или на Set / rolling hash) и дам конкретный оптимизированный фрагмент.
Похожие вопросы