-----------------------------------

klopyrev

Tue Apr 03, 2007 9:49 pm


Palindromes

-----------------------------------

Here is an interesting problem that I have no idea how to solve. I didn't think about it for very long, but all the DP solutions I thought about have flaws in them. If you know how to solve it, feel free to tell me (please). 

Given a string, find the number of UNIQUE palindromes that are subsequences (not substrings). For example, given MADAM:

M, A, D, MM, AA, MAM, MDM, ADA, MAM, MAAM, MADAM. (Hopefully, I didn't miss any)

Have fun and good luck.

KL

PS: Sometimes, its good to misread problems. You come up with new and harder ones. Refer to: http://acm.uva.es/problemset/v3/353.html


-----------------------------------

bugzpodder

Tue Apr 03, 2007 10:26 pm


RE:Palindromes

-----------------------------------

its easy, brute force it.


-----------------------------------

bugzpodder

Tue Apr 03, 2007 10:32 pm


RE:Palindromes

-----------------------------------

this may or may not work.  im hoping it will

f(string x)
  if x.length==0 return 0
  int cnt=0;
  for (i=0;i