|
|
back to boardhint 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 Re: hint 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) |
|
|