Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

DZone's Guide to

# USACO Calfflac Problem

·
Free Resource

Comment (0)

Save
{{ articles[0].views | formatCount}} Views
```// 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

#include

#include

#include

#include

#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;
}

``````
Topics:

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Opinions expressed by DZone contributors are their own.