Z0RR0's blog

Palindrome Partitioning
By Z0RR0, history, 8 years ago, In English

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 ?

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    just solved this problem with the given resources. thanks to all

    → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +72 Vote: I do not like it

.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Is this EERTREE another name for Palindromic Tree? :|

→ Reply