USACO Calfflac Problem

• Tweet
• 

        // Find any largest palindrome in a string no more than 20,000 characters long.
// The file has one or more lines. No line is longer than 80 characters (not counting newline)
// 
// Ignore punctuation, whitespace, numbers, and case when testing for palindromes, but
// keep these extra characters around so you can print them out as the answer.
//
// The largest palindrome is guaranteed to be at most 2,000 characters long before
// whitespace and punctuation are removed.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <ctype.h>

#define MAX_STRING 20001
#define MAX_LINE   81
#define MAX_PAL    2001

typedef struct {
    int begin;
    int end;
} palindex;

int getNextAlpha(char* string, int index) {
    int end = strlen(string);
    while (index++ <= end) {
        if (isalpha(string[index])) {
            return index;
        }
    }
    return end;
}

int getPrevAlpha(char* string, int index) {
    while (index-- >= 0) {
        if (isalpha(string[index])) {
            return index;
        }
    }
    return 0;
}

bool charsAreEqual(char first, char second) {
    return (tolower(first) == tolower(second));
}

int countAlphas(char* string) {
    int x, count = 0;
    for (x = 0; x < strlen(string); x++) {
        if (isalpha(string[x])) {
            count++;
        }
    }
    return count;
}

int countAlphasBetween(char* string, int index1, int index2) {
    int count = 0, x;
    for (x = index1; x <= index2; x++) {
        if (isalpha(string[x])) {
            count++;
        }
    }
    return count;
}

palindex getLargestPal(char* string, int index1, int index2) {
    int length = strlen(string);
    palindex curPal;
    curPal.begin = 0;
    curPal.end = 0;
    int sizeCur = 0, tempidx1 = 0, tempidx2 = 0;

    /* while we haven't exhausted the entire string */
    while (index1 >= 0 && index2 < length) {
        if (charsAreEqual(string[index1], string[index2])) {
            tempidx1 = index1;
            tempidx2 = index2;
            /* crawl each direction and see how big a palindrome you can get */
            while (charsAreEqual(string[getPrevAlpha(string, tempidx1)], string[getNextAlpha(string, tempidx2)]) && (index1 >= 0 && index2 < length)) {
                tempidx1 = getPrevAlpha(string, tempidx1);
                tempidx2 = getNextAlpha(string, tempidx2);
            }   
            if (countAlphasBetween(string, tempidx1, tempidx2) > sizeCur) {
                curPal.begin = tempidx1;
                curPal.end = tempidx2;
                sizeCur = countAlphasBetween(string, curPal.begin, curPal.end);
            }
            index1 = getNextAlpha(string, index1);
            index2 = getNextAlpha(string, index2);
        } else {
            while ((index2 < length) && (!charsAreEqual(string[index1], string[index2]))) {
                index1 = getNextAlpha(string, index1);
                index2 = getNextAlpha(string, index2);
            }
        }
    }

    return curPal;
}

int main(void) {
    FILE *fin, *fout;
    fin = fopen("calfflac.in", "r");
    fout = fopen("calfflac.out", "w");

    char *inText, *totalText, *longPal;
    palindex dice1, dice2;
    inText = malloc(MAX_LINE);
    totalText = malloc(MAX_STRING);
    longPal = malloc(MAX_PAL);
    memset(totalText, 0, MAX_STRING);
    memset(longPal, 0, MAX_PAL);

    while (fgets(inText, MAX_LINE, fin) != NULL) {
        strcat(totalText, inText);
    }

    dice1 = getLargestPal(totalText, 0, 1);
    dice2 = getLargestPal(totalText, 0, 2);
    int sizePal1 = countAlphasBetween(totalText, dice1.begin, dice1.end);
    int sizePal2 = countAlphasBetween(totalText, dice2.begin, dice2.end);

    if (sizePal2 > sizePal1) {
        dice1 = dice2;
    } else if (sizePal2 == sizePal1) { /* swap them if dice2 begins before dice1 */
        if (dice2.begin < dice1.begin) {
            dice1 = dice2;
        }
    }

    strncpy(longPal, &totalText[dice1.begin], (dice1.end - dice1.begin + 1));

    if (NULL != longPal) {
        fprintf(fout, "%d\n%s\n", countAlphas(longPal), longPal);
    }


    return EXIT_SUCCESS;
}

Tags:
• C