Olej писал(а):Взяв за основу одну из
опубликованных реализаций алгоритма Укконена построения суффиксного дерева за линейное время O(n), построил такую вот демонстрационную задачу...
Для сравнения 2 широко обсуждаемых алгоритма построения суффиксного дерева за линейное время O(n): 1-й это Укконен (первоисточник указан), а 2-й - это упрощённый вариант алгоритма Питера Вейнера, рассматриваемый здесь:
Простое суффиксное дерево.
Интересно что?:
Код: Выделить всё
[olej@dell Ukkonen]$ ./ukkonen
> xabxa$
{pos,len,link}: {1:2,4,0} {2:2,4,0} {3:2,4,0} {4:0,2,6} {5:5,1,0} {6:1,1,0} {7:5,1,0} {8:5,1,0}
0: map size 4 : [$,8] [a,6] [b,3] [x,4]
1: map size 0 :
2: map size 0 :
3: map size 0 :
4: map size 2 : [$,5] [b,1]
5: map size 0 :
6: map size 2 : [$,7] [b,2]
7: map size 0 :
8: map size 0 :
узлов 9 рёбер 8 длиной:
4 4 4 2 1 1 1 1 => 18
<8>$[5:1]:$
<6>a[1:1]:a
<7>$[5:1]:$
<2>b[2:4]:bxa$
<3>b[2:4]:bxa$
<4>x[0:2]:xa
<5>$[5:1]:$
<1>b[2:4]:bxa$
> ^C
Код: Выделить всё
[olej@dell Ukkonen]$ ./weiner
> xabxa$
{pos,len,par}: {1:0,1,0} {2:6,1,1} {3:6,1,6} {4:6,1,8} {5:6,4,1} {6:5,1,1} {7:6,4,6} {8:5,2,1} {9:6,4,8}
1: map size 4 : [$,2] [a,6] [b,5] [x,8]
2: map size 0 :
3: map size 0 :
4: map size 0 :
5: map size 0 :
6: map size 2 : [$,3] [b,7]
7: map size 0 :
8: map size 2 : [$,4] [b,9]
9: map size 0 :
узлов 9 рёбер 8 длиной:
1 1 1 4 1 4 2 4 => 18
<2>$[5:1]:$
<6>a[4:1]:a
<3>$[5:1]:$
<7>b[2:4]:bxa$
<5>b[2:4]:bxa$
<8>x[3:2]:xa
<4>$[5:1]:$
<9>b[2:4]:bxa$
> ^C
Видно, что порядок формирования дерева суффиксов в 2-х методах совершенно
разный, узлы дерева перенумерованы по-разному, но конечный вид дерева-графа
совпадает.
Это и понятно, потому что сам цикл формирования дерева в Укконена записан так (побуквенно слева-направо):
Код: Выделить всё
for( unsigned i = 0; i < sinp.size(); i++ )
add_letter( sinp[ i ] );
А у Вейнера (побуквенно справа-налево):
Код: Выделить всё
for( int i = s.size() - 1; i >= 0; i-- )
extend( i );