Изменения

<font color=green>// <tex>s</tex> {{---}} исходный текст</font> <font color=green>// <tex>n</tex> {{---}} длина текста</font> <font color=green>// <tex>t</tex> {{---}} массив, в котором хранится дерево</font> <font color=green>// <tex>sz</tex> {{---}} размер суффиксного дерева</font>

<tex>l, r, par,link</tex> <tex>\mathtt{next}[]</tex> '''function''' <tex>\mathtt{len}():</tex> '''return''' <tex>r - l</tex> '''function''' <tex>\mathtt{get}(c):</tex> '''if''' <tex>!next.count(c)</tex> <tex>\mathtt{next}[c] = -1</tex> '''return''' <tex>\mathtt{next}[c]</tex>

<tex>v</tex> <font color=green>// номер вершины, в которой мы остановились на предыдущей итерации</font> <tex>pos</tex> <font color=green>// позиция на метке ребра, ведущего в эту вершину</font>

'''state''' <tex>ptr(0, 0)</tex> <font color=green>// указатель на конец самого длинного не уникального суффикса</font>

'''function''' <tex>\mathtt{go}(st,</tex> <tex>l,</tex> <tex>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]),</tex> <tex>0)</tex> '''if''' <tex>st.v == -1</tex> '''return''' <tex>st</tex>

'''if''' <tex>\mathtt{s}[\mathtt{t}[st.v].l + st.pos] <tex>\ne \mathtt{</tex> 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,</tex> <tex>st.pos + r - l)</tex> <tex>l = l + \mathtt{t}[st.v].\mathtt{len}() - st.pos</tex> <tex>st.pos = \mathtt{t}[st.v].\mathtt{len}()</tex> '''return''' <tex>st</tex>

'''function''' <tex>\mathtt{split}(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> <tex>\mathtt{node}</tex> <tex>v = \mathtt{t}[st.v]</tex> <tex>id = sz</tex> <tex>sz = sz + 1</tex> <tex>\mathtt{t}[id] = \mathtt{node}(v.l,</tex> <tex>v.l + st.pos,</tex> <tex>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 = \mathtt{t}[st.v].l + st.pos</tex> '''return''' <tex>id</tex>

'''function''' <tex>\mathtt{getLink}(v):</tex> '''if''' <tex>\mathtt{t}[v].link <tex>\ne -1 </tex>-1 '''return''' <tex>\mathtt{t}[v].link</tex> '''if''' <tex>\mathtt{t}[v].par == -1 </tex> '''return''' <tex>0</tex> <tex>to = \mathtt{getLink}(\mathtt{t}[v].par)</tex> '''return''' <tex>\mathtt{t}[v].link=\mathtt{split}(\mathtt{go}(\mathtt{state}(to,</tex> <tex>\mathtt{t}[to].\mathtt{len}()),</tex> <tex>\mathtt{t}[v].l+(\mathtt{t}[v].par==0),</tex> <tex>\mathtt{t}[v].r))</tex>

'''funciton''' <tex>\mathtt{treeExtend}(pos):</tex> '''while''' <tex>true</tex> <tex>\mathtt{state}</tex> <tex>nptr = \mathtt{go}(ptr,</tex> <tex>pos,</tex> <tex>pos + 1)</tex> '''if''' nptr.v <tex>nptr.v \ne -1</tex>-1 <tex>ptr = nptr</tex>

<tex>mid = \mathtt{split}(ptr)</tex> <tex>leaf = sz</tex> <tex>sz = sz + 1</tex> <tex>\mathtt{t}[leaf] = \mathtt{node}(pos,</tex> <tex>n,</tex> <tex>mid)</tex> <tex>\mathtt{t}[mid].\mathtt{get}(\mathtt{s}[pos]) = leaf</tex> <tex>ptr.v = \mathtt{getLink}(mid)</tex> <tex>ptr.pos = \mathtt{t}[ptr.v].\mathtt{len}()</tex> '''if''' <tex>!mid</tex>

'''function''' <tex>\mathtt{buildTree}():</tex> <tex>sz = 1</tex> '''for''' <tex>i = 0...n</tex> <tex>\mathtt{treeExtend}(i)</tex>