Не так давно я выдвинул одну гипотезу, доказать которую у меня не получилось.
Гипотеза:
Пусть у нас есть бор, состоящий из не более, чем N вершин. Возьмем все строки, соответствующие листьям этого бора. Я утверждаю, что в сумме у этих строк будет не более, чем N * K различных суффиксов, где K — размер алфавита.
Я выдвинул эту гипотезу из того соображения, что по такому бору можно построить суфавтомат, и в нем будет не более N * K переходов. Где логическая связь между этим высказыванием и моей гипотезой — именно это мне и хочется узнать.
UPD. Своеобразный feature-request: неплохо было бы иметь возможность убирать свои топики из прямого эфира, не переводя их в черновики.
Не правда же.
Возьмем длинную цепочку из букв a, и повесим в конец полное дерево высоты 2.
Тогда у нас NK^2 суффиксов и (N+K^2) вершин. Понятно что при достаточно большом N NK^2 > NK+K^3.
Она, кажется, неверна. Возьмем строчку s с Ω(N2) различных подстрок, и составим бор из всех префиксов этой строки, к каждому из которых припишем #. В этом боре, очевидно, O(N) вершин, но все различные суффиксы всех этих префиксов -- в точности все различные подстроки s, а таких Ω(N2).
Речь идет не про сжатый бор, а про обычный. А обычный бор по префиксам строки, в которой все символы разные, очевидно, содержит O(N^2) вершин.Я тупой, простите...Можно построить строку из символов 0 и 1, в которой
различных подстрок. См. De Bruijn sequence
Рассмотрим строку aaa..abbb..bc с равным количеством символов a и b. В ней, очевидно, Ω(N2) различных подстрок. Бор всех префиксов этой строки содержит O(N) вершин. Количество различных суффиксов всех префиксов, тем не менее, есть Ω(N2).
Ох, я невероятно тупой (перепутал бор по префиксам строки с бором по суффиксам).
Спасибо всем, гипотеза опровергнута.
Пусть K=3. Построим очень длинную цепочку из букв 'a'. В её конце сделаем раздвоение: 'b'-'c', а на конце каждой из веток ещё по одному — 'b'-'c'. Тогда у нас есть 4 листа, каждому отвечает ~ N различных суффиксов (потому что у каждого из них уникальное окончание либо длина). Имеем ~ 4*N суффиксов.