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 1297. Palindrome

For those who're getting WA19
Posted by jagatsastry 18 Jun 2008 16:39
You must have found the longest common substring of a and rev(a). That method works. But you should also be taking care of false positives like
rewqSOMETEXTqwer. You get rewq while ETE is the answer. So, once you think it's the end of a possible palindrome, have a checker to make sure that IT IS a palindrome and not a false positive sign.
This is the part of my code which does this(I've used the dp method found in wikipedia)
              if(mxLen<lcs[i][j])
              {

                   if(((i==n || j==n) || a[i]!=b[j]))
                      if(checkIfPali(a, i-1, lcs[i][j]))
                                 {
                                  mxPt=j-1;
                                  mxLen=lcs[i][j];
                                 }
              }

Hope this helps many,
Jagat