слишком сложно.

я не понимаю.

предполагается непрерывная последовательность
abcd..xyzabcd...

🙃, понял. В любом случае спасибо

написал такую функцию (на JS), но для больших строк долго работает

function getAllSubstrings(str) {
  let len = str.length;
  let seen = {};

  for (let i = 0; i < len; i++) {
      for (let j = i + 1; j < len + 1; j++) {
        const substr = str.slice(i, j);
        if (! seen[substr]) {
          seen[substr] = 1;
        } else {
          ++seen[substr];
        }
      }
  }
  return seen;
}

console.log(getAllSubstrings('abc'))
{ a: 1, ab: 1, abc: 1, b: 1, bc: 1, c: 1 }

От slice можно избавиться

Если взять число M, и совместить вместе в порядке возрастания все двоичные записи чисел от 0 до 2^M-1 (дозаполненные слева нулями до длины, равной M), то длина получившейся строки S будет M*2^M.

Для любой подстроки S длины хотя бы 3*M можно однозначно восстановить границы, на которых заканчивается одно число и начинается другое. И засчёт этого восстановить информацию о стартовой и конечной позиции.
То есть любая такая подстрока уникальна.

Средняя длина такой подстоки будет O(N), а количество таких подстрок O(N^2).

В результате, для одного лишь создания результата нам в худшем случае понадобится O(N^3) времени и памяти.

То есть при текущем формате результата этот алгоритм асимптотически оптимален

эм... вообще-то список всех подстрок с количеством раз, сколько встречается, можно за линию времени и памяти построить (но выписать за линию времени не получится :) )

> при текущем формате результата

при текущем формате результата - за размер ответа, очевидно

Всем привет! А каким образом можно избавиться?

Только там нужно немного по-другому делать, так как это JS, а в нём конкатенация строк за O(n+m)

Да элементарно индексы только хранить. Если вызывающей стороне нужна строка, то ее можно получить в любой момент. Правда, усложнится заполнение списка.

string_view подойдёт, если на С++ делать seen.
unordered_map<string_view, int> seen;

Тут люди JS-ом обмазываются.

Какого списка, если здесь хеш-таблица?

на самом деле нужно количество этих подстрок, но сделал с помощью хэша для удаленя дублей

Да все равно как называть. В js ассоциативный массив, в c++ map. Потенциально можно результат и в двухмерный массив занести, да во что угодно.

в js объект, в php ассоциативный массив, в perl хэш))