Изменения

Рассмотрим пример реализации дерева палиндромов. Будем считать, что каждая вершина имеет номер. Свободный для очередной вершины номер будем хранить в переменной <tex>nsz</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; 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(link[last])][c]; to[last][c] = sz++; } last = to[last][c]; } Чтобы построить дерево палиндромов, нужно просто для каждого символа исходной строки последовательно вызвать <tex>\mathrm{add_letter}</tex>.