1 Ответ от freele

(15 ответов, оставленных в Problems)

Большое спасибо, за статьи и за ответ.
Попробую это обдумать.
А если ребер нет, то и не проверять. То есть можно флаг "проверено" сделать для узла, и не заходить 2-й раз. Не усложняю?

Перейти к разделу: Problems

2 Ответ от freele

(15 ответов, оставленных в Problems)

Но ведь в таком случае я , возможно, буду в каждое состояние заглядывать не 1 раз, а это может замедлить программу. Разве не так? Или полученный суффиксный автомат нужно было как-то преобразовать?

Перейти к разделу: Problems

3 Ответ от freele

(15 ответов, оставленных в Problems)

Логику я понимаю. И деление, обход, все понятно.
Не ясно, как, делая обход по суффиксным обратным ссылкам в глубину, определить наличие пути по символу из узла.

Вот лог обхода с номером состояния, строкой и ссылками перехода.
2 строки: aba, zab, разделители - цифры. 

v: 0
   longest: 
1 2 4 5 8 
v: 1
   longest: a
3 6 
v: 3
   longest: aba

v: 6
   longest: aba0za

v: 2
   longest: ab
7 
v: 7
   longest: aba0zab

v: 4
   longest: aba0

v: 5
   longest: aba0z

v: 8
   longest: aba0zab1

Как двигаясь по этим ссылкам, определить наличие пути? Или я не так что-то сделал?
Я уже от корки до корки перечитал статьи - про автомат со всеми задачами, найти наибольшую повторяющуюся подстроку оказалось несложно, с двумя тоже все легко. Но я застопорился на том, как определить путь из узла проходом в глубину, двигаясь по суффиксным ссылкам (обратным).

Перейти к разделу: Problems

4 Ответ от freele

(15 ответов, оставленных в Problems)

Здравствуйте.
Та же задача.
Сделал суффиксный автомат, и общая подстрока ищется при проходе по буквам, но это медленный метод.
Пробую организовать проход по инвертированным суффиксным ссылкам, чтобы обойтись за время O(n). Но в таком случае я не понимаю, как проверить, находясь в каком-либо узле, есть ли у него путь, содержащий разделитель.
Я уже кучу версий перепробывал. Или это нужно как-то учесть при построении автомата? Или нужно автомат превратить в дерево?
Не могу понять, как проверить путь, если двигаться не по буквенным ссылкам автомата, которые этот путь и определяют.

Перейти к разделу: Problems