188
правок
Изменения
Нет описания правки
Пусть длина самой короткой строки, которая принимается состоянием <tex>q</tex> равно <tex>k</tex>, тогда '''суффиксная ссылка''' <tex>link_q</tex> будет вести из этого состояния в состояние, которое принимает эту же строку без первого символа.
}}
Будем обозначать длину самой длинной строки, которая принимается состоянием <tex>q</tex> как <tex>len_q</tex>. Длина самой короткой строки из <tex>q</tex> в таком случае будет равна <tex>len_len(link_q) + 1</tex>. Суффиксный автомат может быть построен за линейное время online-алгоритмом. Будем добавлять символы строки <tex>s</tex> по одному, перестраивая при этом автомат. Изначально автомат состоит из одного состояния, для которого <tex>len(0) = 0</tex>, а <tex>link_0 = -1</tex>.<br>Обозначим состояние <tex>last</tex>, соответствующее текущей строке до добавления символа <tex>c</tex> (изначально <tex>last = 0</tex>). <br>Создадим новое состояние <tex>cur</tex>, <tex>len(cur) = len(last) + 1</tex>. <br>Рассмотрим все переходы из <tex>last</tex> по текущему символу <tex>c</tex>. Если перехода нет, то добавляем переход в <tex>cur</tex>, переходим по суффиксной ссылке и повторяем процедуру снова. Если переход существует, то остановимся и обозначим текущее состояние за <tex>p</tex>. Если перехода не нашлось и по суффиксным ссылкам мы дошли до фиктивного состояния (на которое указывает <tex>link_0</tex>), то <tex>link_{link_qcur} = 0</tex>.<br>Допустим, что мы остановились в состоянии <tex>p</tex>, из которого существует переход с символом <tex>c</tex>. Обозначим состояние, куда ведёт переход, через <tex>q</tex>. Рассмотрим два случая:<br># Если <tex>len(p) + 1 = len(q)</tex>, то <tex>link(q) = cur</tex>.<br># В противном случае, создадим новое состояние <tex>new</tex>, скопируем в него <tex>q</tex> вместе с суффиксными ссылками и переходами. <tex>len(new)</tex> присвоим значение <tex>len(p) + 1</tex>. Перенаправим суффиксную ссылку из <tex>q</tex> в <tex>new</tex> и добавим ссылку из <tex>cur</tex> в <tex>new</tex>. Пройдём по всем суффиксным ссылкам из состояния <tex>p</tex> и все переходы в состояние <tex>q</tex> по символу <tex>c</tex> перенаправим в <tex>new</tex>.Обновим значение <tex>last = cur</tex>.
==Реализация==* Переходы хранятся в массиве отображений (ключ {{---}} символ, значение {{---}} номер состояния) <tex>edges</tex>,* Суффиксные ссылки хранятся в массиве <tex>link</tex>, * Длины строк хранятся в массиве <tex>len</tex>. '''func''' addChar(c)''':''' r = newState() <font color="green">// создаём новое состояние и возвращаем его номер</font> p = last '''while''' p >= 0 '''and''' edges[p].find(c) == edges[p].end()''':''' edges[p][c] = r p = link[p] '''if''' p != -1''':''' q = edges[p][c] '''if''' length[p] + 1 == length[q]''':''' link[r] = q '''else:''' new = clone(q) <font color="green">// скопируем состояние <tex>q</tex></font> link[q] = link[r] = new '''while''' p >= 0 '''and''' edges[p][c] == q''':''' edges[p][c] = new p = link[p] last = r
==Источники информации==
