Все неявные продления листов суммарно можно выполнить за <tex>O(n)</tex> ([[#l1|по Лемме 1]]). [[#l2|По Лемме 2]] алгоритм делает не более <tex>2n</tex> явных продлений. Таким образом, в течение всех <tex>n</tex> итерация суммарно выполняется не более <tex>O(n)</tex> продлений, следовательно, с использованием всех приведенных эвристик, алгоритм Укконена работает за <tex>O(n)</tex>.
== Псевдокод Реализация == <font color=green>// <tex>s</tex> {{---}} исходный текст</font> <code style font color= "display: inlinegreen>// <tex>n</tex> {{---block;"}} длина текста</font> string s<font color=green>// <tex>t</tex> {{---}} массив, в котором хранится дерево</font> int n<font color=green>// <tex>sz</tex> {{---}} размер суффиксного дерева</font>
'''struct node ''' int <tex>l, r, par, link</tex> <tex>\mathtt{next}[]</tex> '''function''' <tex>\mathtt{len}():</tex> '''return''' <tex>r - l</tex> map'''function''' <tex>\mathtt{get}(c):</tex> '''if''' <tex>!next.count(c)</tex> <tex>\mathtt{next}[c] = -1<char,int/tex> '''return''' <tex> \mathtt{next}[c]</tex>
'''struct state''' node (int l=0, int r=0, int par=-1) : l(l), r(r), par(par)<tex>v, link(-1) {} int len() return r - l int &get (char c) if !next.count(c) next[c] = -1 return next[c] pos</tex>
node t[MAXN] int sz'''state''' <tex>ptr(0, 0)</tex>
struct state int v, pos state (int v, int pos) : v(v), pos(pos) '''function''' <tex>\mathtt{go} state ptr (0, 0) state go (state st, int l, int r):</tex> '''while ''' <tex>l < r</tex> '''if ''' <tex>st.pos == \mathtt{t}[st.v].\mathtt{len}()</tex> <tex>st = \mathtt{state }(\mathtt{t}[st.v].\mathtt{get}( \mathtt{s}[l] ), 0);</tex> '''if ''' <tex>st.v == -1</tex> '''return ''' <tex>st</tex> '''else''' '''if ''' <tex>\mathtt{s}[ \mathtt{t}[st.v].l + st.pos ] != \ne \mathtt{s}[l]</tex> '''return ''' <tex>\mathtt{state }(-1, -1)</tex> '''if ''' <tex>r-l < \mathtt{t}[st.v].\mathtt{len}() - st.pos</tex> '''return ''' <tex>\mathtt{state }(st.v, st.pos + r-l)</tex> <tex>l += \mathtt{t}[st.v].\mathtt{len}() - st.pos</tex> <tex>st.pos = \mathtt{t}[st.v].\mathtt{len}()</tex> '''return ''' <tex>st</tex>
int '''function''' <tex>\mathtt{split }(state st):</tex> '''if ''' <tex>st.pos == \mathtt{t}[st.v].\mathtt{len}()</tex> '''return ''' <tex>st.v</tex> '''if ''' <tex>st.pos == 0</tex> '''return ''' <tex>\mathtt{t}[st.v].par</tex> node <tex>v = \mathtt{t}[st.v]</tex> int <tex>id = sz++</tex> <tex>\mathtt{t}[id] = \mathtt{node }(v.l, v.l+st.pos, v.par)</tex> <tex>\mathtt{t}[v.par].\mathtt{get}( \mathtt{s}[v.l] ) = id</tex> <tex>\mathtt{t}[id].\mathtt{get}( \mathtt{s}[v.l+st.pos] ) = st.v</tex> <tex>\mathtt{t}[st.v].par = id</tex> <tex>\mathtt{t}[st.v].l += st.pos</tex> '''return ''' <tex>id</tex>
int get_link '''function''' <tex>\mathtt{getLink}(int v):</tex> '''if ''' <tex>\mathtt{t}[v].link != \ne -1</tex> '''return ''' <tex>\mathtt{t}[v].link</tex> '''if ''' <tex>\mathtt{t}[v].par == -1</tex> '''return ''' <tex>0</tex> int <tex>to = get_link \mathtt{getLink}(\mathtt{t}[v].par)</tex> '''return ''' <tex>\mathtt{t}[v].link = \mathtt{split }(\mathtt{go }(\mathtt{state}(to,\mathtt{t}[to].\mathtt{len}()), \mathtt{t}[v].l + (\mathtt{t}[v].par==0), \mathtt{t}[v].r))</tex>
void tree_extend '''funciton''' <tex>\mathtt{treeExtend}(int pos):</tex> '''for'''<tex>(;;)</tex> state <tex>nptr = \mathtt{go }(ptr, pos, pos+1)</tex> '''if ''' <tex>nptr.v != \ne -1</tex> <tex>ptr = nptr</tex> '''return''' int <tex>mid = \mathtt{split }(ptr)</tex> int <tex>leaf = sz++</tex> <tex>\mathtt{t}[leaf] = node (pos, n, mid)</tex> <tex>\mathtt{t}[mid].\mathtt{get}( \mathtt{s}[pos] ) = leaf</tex> <tex>ptr.v = get_link \mathtt{getLink}(mid)</tex> <tex>ptr.pos = \mathtt{t}[ptr.v].\mathtt{len}()</tex> '''if ''' <tex>!mid</tex> '''break'''
void build_tree'''function''' <tex>\mathtt{buildTree}():</tex> <tex>sz = 1</tex> '''for (int ''' <tex>i=0; i...n<n; ++i)/tex> tree_extend <tex>\mathtt{treeExtend}(i)</codetex>
== См. также==
