275
правок
Изменения
м
→Реализация
'''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>
'''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>
<tex>id = sz</tex>
<tex>sz = sz + 1</tex>
<tex>\mathtt{t}[id] = \mathtt{node}(v.l, 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>
'''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''' <tex>nptr.v \ne -1</tex>
<tex>ptr = nptr</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>
