Таким образом, суммарное время работы построения алгоритма <tex>O(n)</tex>.
== Реализация ==
Рассмотрим пример реализации дерева палиндромов. Будем считать, что каждая вершина имеет номер. Свободный для очередной вершины номер будем хранить в переменной <tex>sz</tex>.
Для каждой вершины будем хранить длину палиндрома, суффиксную ссылку и массив ребер. В реализации им будут соответствовать массивы <tex>len[\mathrm{MAXN}]</tex>, <tex>suff\_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];
'''int''' n, sz, last;
В самом начале нужно инициализировать структуру.
'''void''' init() {
n = 0;
suff_link[0] = 1;
len[1] = -1;
sz = 2;
}
Вспомогательная функция, которая спускается начиная с вершины <tex>v</tex> по суффиксным ссылкам до тех пор, пока не придет в палиндром-суффикс <tex>xAx</tex>. Тут <tex>x</tex> {{---}} последний добавленный символ, а <tex>A</tex> {{---}} некоторый палиндром.
'''int''' get_sufflink('''int''' v) {
'''while''' (s[n - len[v] - 2] != s[n - 1]) v = suff_link[v];
'''return''' v;
}
И, наконец, процедура добавления очередного символа в структуру:
'''void''' add_letter('''int''' c) {
s[n++] = c;
last = get_sufflink(last);
'''if''' (!to[last][c]) {
len[sz] = len[last] + 2;
link[sz] = to[get_sufflink(suff_link[last])][c];
to[last][c] = sz++;
}
last = to[last][c];
}
Чтобы построить дерево палиндромов, нужно просто для каждого символа исходной строки последовательно вызвать <tex>\mathrm{add\_letter}</tex>.
== Применения ==
