Sunday, December 5, 2010

USACO - Calf Flac

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 the 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

Greedy - longest palindrome with size less than 2000 - brute force

In this problem you have a string with size 20,000 and want to find the longest palindrome with size less than 2000, but there are non-alphabetical characters in the input file. So I first read input, I have two arrays for input, one is the input and the other is the transformed input and indexing of the alphabets that I have saved in lower case.
Then I iterate from 0 to size of input and each time I check two things: First : if current character is the middle character, how much can we extend the palindrome from left and right, So I iterate 1000 to left and 1000 to right and wherever it's not yet a palindrome I stop continuing to expand the palindrome,this is when the size of the palindrome is odd, when the size of the palindrome is even I set the current and next character as the core of my palindrome with size even, and again expand the current palindrome. In this approach time complexity is O(20,000 * 2000).

2 comments:

  1. Great Idea
    I think about the same thing but the only difference between me and you that i am putting the file into one only string, and I skip checking the letters that are not alphabete

    ReplyDelete
  2. Hello, I've a same website like you. pls visit: http://solvingalgorithms.blogspot.com

    ReplyDelete

USACO - Prime Palindromes

I just skimmed the problem statement and panicked of the high boundary of the input, but something inside told me don't worry everyth...