USACO 1.3.3 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

SOLUTION

This problem was a real pain and very difficult for me… First of all, I thought the palindromes were to be found on each line but they were actually supposed to be found throughout the entire input.  After I resolved that, I found that the algorithm I was using was too slow.  After getting frustrated and trashing my initial program, I searched online for a better algorithm…

You create two strings of the input, one is the raw input and one has only the letters.  You walk through each character of the string with letters treating each letter as the centre of a palindrome.  You expand from the centre checking if the left side is equal to the right side.  The longest match between right and left side is the longest palindrome with a center at that point.

There are two kinds of palindromes:  even length and odd length.  We have to check both types.

I decided to write this in c++, even though I’m not very familiar with the language, because it runs faster than Java.

Here is the code in c++

/*
ID: frigid.1
PROG: calfflac
LANG: C++
*/

#include <iostream>
#include <fstream>
#include <string>

   using namespace std;

   char s[20000], ss[20000];
	int slen, sslen;
	int maxp, maxq, maxl = 0;
	
	int findpal (int p, int q) {
		int i, j;
		while (ss[p] == ss[q] && p >= 0 && q < sslen) {
			i = p;
			j = q;
			p--;
			q++;
		}
		if (j - i + 1 > maxl)
		{
			maxp = i;
			maxq = j;
			maxl = j - i + 1;
		}
	}
	
   int main() {
   
      ofstream fout ("calfflac.out");
      ifstream fin ("calfflac.in");
	 	char c;
      slen = 0;
		sslen = 0;
    	
      while (fin.get(c)) {
			s[slen] = c;
			slen++;
			if (isalpha(c)) {
				ss[sslen] = tolower(c);
				sslen++;
			}
		}
		
		for (int i = 1; i < sslen; i++) {
			//odd palindrome
			findpal (i - 1, i + 1);
			//even palindrome
			findpal (i - 1, i);
		}
		
		string output = "";
		int alpha = -1;
		
		for (int i = 0; i < slen && maxq >= alpha + 1; i++) {
			if (isalpha (s[i]))
				alpha++;
			if (maxp <= alpha && maxq >= alpha)
				output += s[i];
		}
		
		fout << maxl << endl;
		fout << output << endl;
   
      return 0;
   
   }

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: