165
правок
Изменения
→Реализация
Рассмотрим пример реализации дерева палиндромов. Будем считать, что каждая вершина имеет номер. Свободный для очередной вершины номер будем хранить в переменной <tex>sz</tex>.
Для каждой вершины будем хранить длину палиндрома, суффиксную ссылку и массив ребер. В реализации им будут соответствовать массивы <tex>len[\mathrm{MAXN}]</tex>, <tex>suff_linksuff\_link[\mathrm{MAXN}]</tex> и <tex>to[\mathrm{MAXN}][\mathrm{ALPHABET\_SIZE}]</tex> соответственно. Также будем хранить саму строку и длину ее обработанной части <tex>n</tex>. В переменной <tex>last</tex> будем хранить последнюю добавленную вершину.
'''int''' s[MAXN], len[MAXN], suff_link[MAXN], to[MAXN][ALPHABET_SIZE];
}
Чтобы построить дерево палиндромов, нужно просто для каждого символа исходной строки последовательно вызвать <tex>\mathrm{add_letteradd\_letter}</tex>.
== Применения ==
