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