1

Тема: Суффиксный автомат

Можете написать, что за переменная nlast в реализации алгоритма?

2

Re: Суффиксный автомат

nlast == cur

3

Re: Суффиксный автомат

Спасибо! Получается опечатка. smile

4

Re: Суффиксный автомат

fixed

5

Re: Суффиксный автомат

Кстати, вроде бы в этой статье есть еще опечатка в разделе о нахождении позиции первого вхождения. Там где написано "При клонировании вершины q в clone мы ставим: firstpos(clone) = firstpos(cur)". Видимо, должно быть "firstpos(clone) = firstpos(q)".

6

Re: Суффиксный автомат

Мне кажется лишним замечание про якобы совпадение множеств endpos у t0 и "a" здесь. Множеству endpos для состояния s однозначно соответствует набор суффиксов строки (включая пустой), которые принимает автомат из данного состояния (т.е. суффиксов, которые следуют за вхождениями подстрок, соответствующих s). Состояние t0 отличается от всех остальных как минимум тем, что для него в такое множество суффиксов входит суффикс, соответствующий всей строке (и мощность endpos для t0 равна длине строки + 1 - учитываются все суффиксы от пустого до всей строки). Из состояния "a" в суффиксном автомате строки S="aa..aa", напротив, не принимается вся строка S, только её собственные суффиксы, и |endpos("a")| = length(S).
Если принять нумерацию позиций в endpos "за концом строки", как в STL, то каждая позиция в endpos есть начало соответствующего суффикса, и тогда endpos(t0) = [0...length(S)], endpos("a") = [1...length(S)]. Если же нумерация как в статье, нужно отнять отовсюду по единице: endpos(t0) = [-1...length(S) - 1], endpos("a") = [0...length(S) - 1], считая, что самое левое вхождение пустой строки - [0..-1].

7

Re: Суффиксный автомат

Что такое автомат??? С википедии ничего не понятно, а гугл дает оружие.