Пятничные задачки для программистов.

← →
TUser © (2006-05-02 11:56) [40]

Я тоже не знаю. Есть алгоритм Укконена, который позволяет строить суффиксное дерево за линейное время. А обход дерева, вроде бы, должен занимать как раз N log N, т.к. логарифм - это средняя высота листа, а всего листьев - O(N). Только вот не уверен.

Квадратичный алгоритм :))

for i:=0 to high do
sum := 0
for j:=i to high do
sum += A[j]
if sum = WhatWeNeed then
returm i, j

← →
MBo © (2006-05-02 12:37) [41]

>TUser © (02.05.06 11:56) [40]
Можно и несколько другим квадратичным алгоритмом воспользоваться:
Построить массив частичных сумм за линейное время
s[0]=A[0]
s[i] = s[i-1]+A[i]
Затем квадратичная часть - сравнение разностей s[i]-s[j] c искомой суммой.

Отсюда осталась пара шагов модификации до NlogN...

Пятничные задачки для программистов. Найти похожие ветки