Блог пользователя daftcoder

Вопрос: нахождение наибольшей общей подстроки суффиксным деревом
Автор daftcoder, 13 лет назад, По-русски

Собственно, вопрос такой: можно ли решать эту задачу пропусканием второй строки по дереву первой? Убил весь вечер, переписал кучу квадратоподобных вариантов, но они даже не были верными.

P.S.: Как делать это, строя дерево для сконкатенированной строки, знаю.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Должно быть что-то подобное:
Строим суффиксное дерево для строки S.
Теперь пропускаем поочередно каждый символ ch T через суффиксное дерево поддерживаю длину наибольшей общей подстроки (length):
Если есть переход по ch, то переходим и length++, если не можем перейти, то идем по суффиксным ссылкам до тех пор пока не дойдем до корня, либо до вершины из которой есть ребро по символу ch, во втором случае, делаем переход по символу ch и ставим length в длину от корня дерева, а в первом случае равным 0.
После переходим к следующему символу строки T.
На каждом этапе обновляем ответ.

http://e-maxx.ru/algo/suffix_automata там можно поглядеть как выглядит это для суффиксного автомата.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Логика суфф. автомата сюда возможно не подходит :-( Напоролся на проблему того, куда нам переходить, если мы сейчас в середине ребра. Вроде логично, что нужно сохранить длину пройденного пути, пройти по суффиксной ссылке отца, а потом попытаться заново отложить этот отрезок. Если не получается - снова идём по ссылке... Попробую дописать это сегодня. Вечером наверное сообщу результат.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Переходим по суф. ссылке и канонизируем получившееся состояние. Можно доказать что это всегда получится
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А можно немножко на пальцах объяснить тест с деревом по строке AABAAAA и пропускаемой строкой AAABAAA? По первым трём A пройдём в 6 ребро и там встанем на первой букве. Затем будет B во второй строке, что делаем дальше?
        → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Переходим по ссылке в корень и допрыгиваем до буквы B в первом ребре?
        → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    То же самое начал писать, но потом понял, что тогда мы должны будем уметь искать суфф.ссылку для состояния посередине ребра. Если делать это "в лоб" (поднимаясь до предка, потом спускаясь), то будет квадрат же...
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Линия в сумме будет, т.к. каждая пройденная при канонизации вершина укорачивает "хвост", а он растет не более чем на 1 за шаг
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
можно ещё построить суффиксное дерево для строки "S@T" (@ это символ разделитель), а затем найти самую глубокую вершину которая в своем поддереве содержит лист который соответствует префиксу строки который заканчивается до и лист префикс которого заканчивается после разделяющего символа... глубина этой вершины и будет ответом... как-то так...
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да, так я умею (в ps написано), вопрос был в том, как это сделать без построения дерева по второй строке.
    → Ответить
13 лет назад, # |
← Rev. 7   Проголосовать: нравится 0 Проголосовать: не нравится

Мое решение: http://pastebin.com/U5ZJVV6F

P.S. Когда наконец поправят отправку комментариев из chrome?
→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В исходном тексте Укконена в процедуре test-and-split(s, (k, p), t) есть такие строчки:

let g'(s, (k', p')) = s' be the t_k-transition from s; if t = t_{k' + p - k + 1} then return(true, s)

Мне не понятен смысл состояния s' и индексов k', p'. Что они означают?

→ Ответить