ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1635. Mnemonics and Palindromes

hint
Posted by ASK 21 Nov 2010 22:06
Build a data-structure which allows O(1) test that s[from..to] is a palindrome. The structure is a 2 x s.size() array: even/odd length times possible center point.

typedef vector<int> V;
string s(4001, ' ');
int n;
V mpl[2]; // maximum palindrome length around i (even and odd lengths)
inline bool is_polindrome(int from, int to){
  assert(0 <= from and from < to and to <= n);
  int eo = (to - from) % 2, c = (from + to) / 2;
  return mpl[eo][c] >= c - from;
}
Re: hint
Posted by marat 12 Apr 2011 03:53
One can think like that:
Let a(k) be the amount of palindromes in [0,k]. Then we have recursion:
a(k)=MIN{ 1 if [0,k] is pm  , MIN (from i = 0 to k -1) OF a(i) + 1   if [i,k] is pm}
        { 0 else                                          a(i) + k-i else          }

I consider ASK to be absolutely right concerning data structure He proposed.

Re: hint
Posted by net 18 Jul 2011 15:12
And implemntataion by this idea =)
http://pastebin.com/6bGHLipR
Re: hint
Posted by chomu1850 22 Nov 2015 20:44
Considering each character as a pivot, expand on both sides to find the length of both even and odd length palindromes centered at the pivot character under consideration and store the length in the 2 arrays (odd & even).
Time complexity for this step is O(n^2)