WXR's blog

A problem of B. Palindrome
By WXR, 13 years ago, In English

I got an idea of this problem.
First we reverse this string, then we use dp to find the LCS of these two strings. Using dp will take O(2n) space, but will use O(n^2) time. TLE! Is there anybody to help me? Thanks!

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

»
13 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

You can limit n to 2600 (26 lower case Latin letters * maximum required palindrome length 100).

→ Reply
»
12 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Use Suffix Automation to approach it.

→ Reply