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

Palindrome Partitioning
Автор Z0RR0, история, 8 лет назад, По-английски

is there any O(n) or O(nlogn) solution to find minimum number of partition of a string where each partition is a palindrome ? there is simple O(n^2) dp solution for this. but is there any greedy insight or any better solution to make it better than the normal dp solution ?

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

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Yes, there is an O(nlogn) algorithm, and also a data structure called EERTREE which can solve it.
Here are the two papers.
A Subquadratic Algorithm for Minimum Palindromic Factorization
EERTREE: An Efficient Data Structure for Processing Palindromes in Strings

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Here's similar problem where you can test it http://acm.timus.ru/problem.aspx?space=1&num=2058

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I have solved a similar problem before. You can solve it with some preprocessing and shortest path modelling using dijkstras or dfs, but the problem constants were not too big, and i think the complexity of my solution will be O(n2) like your dp algorithm.

→ Ответить
»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится +72 Проголосовать: не нравится

.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    thank you for this wonderful data structure. I am recovering from aibohphobia with the help of eertree :D

    → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Is this EERTREE another name for Palindromic Tree? :|

→ Ответить