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

Timus - 1297. Палиндромы
Автор Planshetnik, 14 лет назад, По-русски
Здравствуйте!
Пожалуйста подскажите как решить, используя суффиксные деревья или массивы.

Самое очевидное решение (не верное):
Надо сгенерироать все подстроки и включить их в бор, а потом перевернуть строку и снова сгенерировать все подстроки от перевернутой строки и проверить есть ли что-то в боре из этого набора (начиная с самой большой подстроки).

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

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

можно динамикой =)


http://e-maxx.ru/algo/palindromes_count

а лучше вот тут почитать))

→ Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
А зачем там суффиксные деревья? Можно в лоб за O(N2): зафиксировать середину палиндрома и расширять его в обе стороны. Ну а если хочется за O(N), то можно воспользоваться алгоритмом отсюда

PS: Опоздал :)
→ Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Просто читал презентацию там на слайде 8, написано что можно решить именно эту задачу суффиксным деревом. Вот хочу узнать как.
→ Ответить
  • 14 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
    Rendering to html failed: Transformation failed: Unclosed math text.
    → Ответить
    • 14 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Так постараюсь без специальных символов написать коментарий...

      берем строку исходная + странный символ + перевернутая исходная + другой странный символ(большая строка), теперь если мы захотим узнать какой максимальный палиндром с каким-то центром, то надо взять два суффикса (ровно на тех позициях на которых стоит наш символ в большой строке) и найти их наибольший общий префикс, это будет нашим нерасширяемым палиндромом, ну а находить этот префикс может и массив и дерево
      → Ответить
14 лет назад, # |
← Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Научите меня нормально писать комментарии.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    1. Не использовать знак доллара, если не хочешь математическую формулу.
    2. Не использовать ctrl-v. Если очень надо, можно потом зайти в html разметку и убить все теги с charset. Либо сразу вставлять в html разметку

    Надо бы это в FAQ добавить.
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Решение через суффиксные массивы, про которое я писал не правильное -- не обязательно нужно рассматривать соседние суффиксы.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
На емаксе описан алгоритм нахождения подпалиндромов, рботающий за O(N)
→ Ответить