1 Отредактировано maksay (2009-06-20 14:37:40)

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

Пытался разобраться с алгоритмом построения суффиксного автомата, но 3 вещи так и не смог понять. Нельзя ли уточнить:
1).
Суффиксная ссылка link для состояния p определяется следующим образом. Рассмотрим наидлиннейший путь из состояния Init в p, ему соответствует некоторая строка. Суффиксная ссылка не определена только для начального состояния Init. Найдём такой наибольший суффикс этой строки, что ему (этому суффиксу) соответствует некоторое состояние q, отличное от p. Из самого определения следует, что суффикс может быть только собственным, а length[p] > length[q].

Почему такой путь единственен?

2).
int clone = sz++;
st[clone].length = st[p].length + 1;
memcpy (st[clone].next, st[q].next, sizeof st[clone].next);
st[clone].link = st[q].link;
for (; p!=-1 && st[p].next[c]==q; p=st[p].link)
    st[p].next[c] = clone;
st[q].link = st[nlast].link = clone;

Код для случая 2б:

Мы же ничего не знаем об этом, пусть единственном, длиннейшем пути из Init в q.
Почему же тогда

а). st[clone].link = st[q].link;
раз мы ничего не знаем про путь в q.

б).st[q].link = clone;
Аналогичный вопрос, если нам не известно про длиннейшую строку в q ничего, кроме того что она имеет вид не U+C, то почему строка U+C будет ее суффиксом?

Спасибо

PS: Для первого вопроса я приблизительно понимаю, как это можно доказать по индукции, но факт все же, как мне кажется, остается не очевидным

2

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

Есть такой факт: если мы рассмотрим все строки, которые приводят к одному и тому же состоянию, то для любой пары таких строк одна из них будет суффиксом другой. Я вроде упоминал об этом, но вскользь и без доказательства. Пожалуй, это надо будет включить в статью.

Насколько я понимаю, этот факт отвечает на вопросы 1 и 2.

3

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

Ага, спасибо! Оно действительно отвечает на вопросы и несложно доказывается по индукции, так что вопрос снят.

4

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

Непонятно, почему там повторяющиеся множители не вынесены за скобки.
В результате шесть умножений вместо трёх.

If you are looking for fast success in 640-722 then join today to find complete testing ccna pdf notes - pass-4sure and pass passguide network+ tutorial pdf on first try.