1

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

Если мы пройдём из начального состояния t0 по любому пути до какого-либо терминального состояния, и выпишем при этом метки всех пройденных дуг, то получится строка, которая обязана быть одним из суффиксов строки s.

... а терминальные состояния — отмечать звёздочкой.

...

Для строки s = "ab":
http://e-maxx.ru/algo/suffix_automaton_sample_4.gif

Взаимоисключающие параграфы, или я неправильно понял статью? На иллюстрации состояние из t0 через 'a' показано терминальным, но строка "a" не является суффиксом строки "ab".

2

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

Ошибка в иллюстрации... Состояние для строки "a" не является терминальным.

Спасибо, исправлю.

3

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

В этой иллюстрации тоже есть ошибка?
http://e-maxx.ru/algo/suffix_automaton_link.gif
От корневой вершины по дуге 'C', приходит в вершину 'BC'.

4

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

Исправил наконец первую иллюстрацию (всё никак не мог отыскать программу, с помощью которой я их делал: оказалось, это yEd Graph Editor).

Hack-Yer

В этой иллюстрации тоже есть ошибка?

Вроде нет ошибок. Вершине "bc" также соответствует строка "c". Вершине "abcb" также соответствуют её суффиксы "bcb", "cb". Это можно понять с помощью правого рисунка: каждому состоянию соответствует строка, написанная на нём, а также несколько её суффиксов - вплоть до того суффикса, который записан по link'у из этого состояния.

5

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

Вопрос по endpos-окончаниям.
Что подразумевается под " множествов всех позиций в строке s, в которых оканчиваются вхождения строки t"? Это конкретный последний символ для каждой построки (судя по термину "окончание")?
Допустим, для строки "abcaba" и подстроки "caba" endpos будет "а" или "aba, ba, a"? Или что-то третье?

6

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

noktigula
Имеются в виду именно индексы позиций (во всей статье - индексы нумеруются, начиная с нуля). Для строк s="abcaba" будет endpos("caba")={5}, а, например, endpos("a")={0,3,5}.

7

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

Спасибо, и еще один вопрос, про суффиксные ссылки.

"суффиксная ссылка  ведёт в такое состояние, которому соответствует наидлиннейший суффикс строки w, находящийся в другом классе endpos-эквивалентности"

Каким образом суффикс строки w может находится в другом классе? Ведь согласно лемме 1, все суффиксы строки должы быть endpos-эквивалентными?

8

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

noktigula пишет:

Спасибо, и еще один вопрос, про суффиксные ссылки.

"суффиксная ссылка  ведёт в такое состояние, которому соответствует наидлиннейший суффикс строки w, находящийся в другом классе endpos-эквивалентности"

Каким образом суффикс строки w может находится в другом классе? Ведь согласно лемме 1, все суффиксы строки должы быть endpos-эквивалентными?

Нет, почему же эквивалентными: ведь суффикс строки w мог встречаться где-то ещё, помимо вхождений непосредственно внутри w. Например, на строке "aa" для w="aa" суффиксная ссылка из него ведёт в состояние, соответствующее строке "a" - потому что endpos("aa")={1}, endpos("a")={0,1}.