313
правок
Изменения
→Наивный алгоритм
'''void''' insert('''int''' l, '''int''' r):
cur = 0
'''while''' (l < r) '''if''' (go[cur][s[l]].v = -1 ) <span style="color:Green">// если мы не можем пойти из вершины по символу <tex> l </tex></span> createVertex(cur, l, r) <span style="color:Green">// создаем новую вершину</span>
'''else'''
start = go[cur][s[l]].l
finish = go[cur][s[l]].r
hasCut = ''false''
'''for''' j = start '''to''' finish <span style="color:Green">// для каждого символа на ребре из текущей вершины</span> '''if''' (s[l+j-start] != s[j] ) <span style="color:Green">// если нашли не совпадающий символ</span>
<span style="color:Green">// создаем вершину на ребре</span>
old = go[cur][s[l]]
hasCut = ''true''
'''break'''
'''if''' (!hasCut)
cur = go[cur][s[l]].v <span style="color:Green">// переходим по ребру</span>
l = l + finish - start <span style="color:Green">// двигаемся по суффиксу на длину подстроки, записанной на ребре</span>
