275
правок
Изменения
→Реализация
'''struct state'''
<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>
'''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>
'''funciton''' <tex>\mathtt{treeExtend}(pos):</tex>
'''while''' <tex>true</tex>
<tex>\mathtt{state}</tex> <tex>nptr = \mathtt{go}(ptr, pos, pos + 1)</tex>
'''if''' <tex>nptr.v \ne -1</tex>
<tex>ptr = nptr</tex>
