USACO: PROB Calf Flac

[zero-impact]

Quote:

Calf Flac

It is said that if you give an infinite number of cows an infinite number of heavy-duty laptops (with very large keys), that they will ultimately produce all the world's great palindromes. Your job will be to detect these bovine beauties.

Ignore punctuation, whitespace, numbers, and case when testing for palindromes, but keep these extra characters around so that you can print them out as the answer; just consider the letters `A-Z' and `a-z'.

Find any largest palindrome in a string no more than 20,000 characters long. The largest palindrome is guaranteed to be at most 2,000 characters long before whitespace and punctuation are removed.
PROGRAM NAME: calfflac
INPUT FORMAT
A file with no more than 20,000 characters. The file has one or more lines. No line is longer than 80 characters (not counting the newline at the end).
SAMPLE INPUT (file calfflac.in)

Confucius say: Madam, I'm Adam.

OUTPUT FORMAT

The first line of the output should be the length of the longest palindrome found. The next line or lines should be the actual text of the palindrome (without any surrounding white space or punctuation but with all other characters) printed on a line (or more than one line if newlines are included in the palindromic text). If there are multiple palindromes of longest length, output the one that appears first.
SAMPLE OUTPUT (file calfflac.out)

11
Madam, I'm Adam

So far I have tried the brute force solution by just checking all the substrings from biggest to smallest to see if they are palindromes, which has O(n^3) time complexity as far as I can tell. It fails (1.2s ) on the 4th test. I have also tried copying a reversed string into another variable and checking for the longest common substring between the two (courtesy of slatpro) but I see now that that is basically my fist attempt in a different form.

I'm not sure what to try from here. I have been told to try using a suffix array/tree? I'm not quite sure on how to implement this for this problem.

Any other ideas? Is there something obvious I'm overlooking?

All help is appreciated.

[saltpro15]

slatpro indeed : P hmmph

I found that article about how to find palindromes in linear time. It didn't make much sense to me, but you're welcome to try. Cheers, hopefully we get this one soon.

[bbi5291]

Actually, the LCS approach takes "straight" O(n^2) time if you use DP (this will still most likely time out). It can be made to run in O(n) using a suffix tree/array, but of course that is overkill for chapter 1.
The official solution is O(n^2), though. It's quite clever for chapter 1, so I'm not going to give it away. Kudos if you get a linear-time solution up-and-running, but that sorta defeats the purpose of USACO training.

[A.J]

I actually did use the suffix tree algorithm for this question. I don't really feel that it is overkill for Ch 1; on the contrary, I feel that it is really good practice for certain other questions that you might encounter.

Having said that, I still do agree with Brian. The given O(n^2) algorithm, although pretty straightforward, is pretty insightful and clever.

[bbi5291]

You actually coded a suffix tree? Which algorithm did you use? PM me your code... (Wow, you are really starting to scare me :O)

[riveryu]

Hi zero-impact, I'm going to "expand" on bbi5291's helpful hint. My first thought is to brute force just like your solution. It doesn't work from what you said for USACO. For me its natural checking from the ends of a palindrome towards the center, but this is redundant. Why am I scanning through the same place again and again?

So here's the hint I hope you get it: check if a string is palindrome from the center.

This is the first time I see that problem and I've never coded a solution. I'm not sure if what I think is a solution is feasible within the time bound. (It should be O(n^2) though.)

[bbi5291]

riveryu's solution is the same as the official solution. It is worst-case O(N^2) but even a slight deviation from worst-case drastically reduces the runtime, so it works fine on USACO.

[zero-impact]

While I was at work today I expanded on a previous idea I had, and it should be O(N*M).
Just go through the string from the beginning and for each character use that as the center of the palindrome. (as riveryu said). I guess I will have to treat even lengthed palindromes differently than odd lengthed ones. I figure O(N*M) because the problem states that the length of the palindrome will not exceed 2000.

Hopefully I will be able to code this up tonight.

[A.J]

I believe that that is still O(N^2).

[bbi5291]

How is it not O(NM)? You won't be doing more than O(M) operations for each of O(N) positions... (Of course, it is also O(N^2), because of the way big-O notation is defined. But O(NM) is a better bound.)

[A.J]

Please forgive me, Brian, as I tend to take the pessimistic route about life.

[bbi5291]

I guess if they didn't tell you the bound on M then they could give you a pathological case like a string consisting of 20000 a's. Then you'd have to examine approximately N^2 characters (the calculation is left as an exercise to the reader - calculating constant factors can be useful). That seems just a bit too slow to get AC on USACO (although it would probably AC on the PEG Judge.)

[riveryu]

I think there was a reason why they bounded the palindrome to be 2000. Perhaps as a hint? I don't know.

@ bbi5291
Whats AC? Alternating Current??

[A.J]

it's All Correct

[bbi5291]

I guess it could be interpreted that way, but all the English-language online judges seem to use "accepted".