Мне кажется лишним замечание про якобы совпадение множеств 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].
Страницы 1