275
правок
Изменения
→Реализация
<tex>v, pos</tex>
'''state''' <tex>ptr(0, 0)</tex> <font color=green>// указатель на конец самого длинного не уникального суффикса</font>
'''function''' <tex>\mathtt{go}(st, l, r):</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 = l += \mathtt{t}[st.v].\mathtt{len}() - st.pos</tex>
<tex>st.pos = \mathtt{t}[st.v].\mathtt{len}()</tex>
'''return''' <tex>st</tex>
'''return''' <tex>\mathtt{t}[st.v].par</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, 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 = l += st.pos</tex>
'''return''' <tex>id</tex>
'''funciton''' <tex>\mathtt{treeExtend}(pos):</tex>
'''forwhile'''<tex>(;;)true</tex>
<tex>nptr = \mathtt{go}(ptr, pos, pos + 1)</tex>
'''if''' <tex>nptr.v \ne -1</tex>
'''return'''
<tex>mid = \mathtt{split}(ptr)</tex>
<tex>leaf = sz</tex> <tex>sz = sz++1</tex>
<tex>\mathtt{t}[leaf] = node(pos, n, mid)</tex>
<tex>\mathtt{t}[mid].\mathtt{get}(\mathtt{s}[pos]) = leaf</tex>
