Решил задачу 427D - Match & Catch с помощью суффиксного дерева. Однако мое решение за O(N) (6579114) работало дольше, чем решения за O(n²) — 717 мс и кушало ~200 мб памяти!

Сразу нашелся тест, на котором локально это решение работало долго (около 5,8 секунды!!!):

aaa...aa

aaa...aa

Стал разбираться. Выяснилось, что по ходу построения дерева, создается ~12,5 млн. позиций в дереве (объект, который указывает на вершину в сжатом боре). Эти объекты я создавал в куче, через new. Это удобно тем, что можно вернуть указатель на NULL (например, при попытке перехода из вершины по символу).

Я, конечно, знал, что выделение памяти в куче работает дольше, чем на стеке, но не в 15 же раз! :) Вообще, изначально я хотел избавиться от new из-за лишнего потребления памяти: в каждой позиции хранится указатель на вершину(4 байта) + номер буквы на ребре(4 байта) * 12,5 млн.  ≈  100 мб.

В итоге без использования new мое решение получило AC (6579111) за 171 мс, при этом потребляя 2 мб памяти.

У меня только 2 вопроса:

Почему 200 - 100 = 2

И почему локальное время выполнения так сильно отличается от серверного(без new стало работать быстрее на 1 секунду, но 4,8 и 0,17 — все же большая разница)

Заранее спасибо