USACO Current Problems Problem 'shortpal' Analysis

by Neal Wu

Let S denote the string of cows. First, note that we can 'reflect' S after itself (for example, "abc" would become "abccba") to obtain a palindrome of length 2N. We can also reflect all the but the last character (for example, "abc" would become "abcba") to obtain a palindrome of length 2N - 1.

Continuing in this way, we can see that if S ends with a palindrome of length L, then we can reflect the first N - L characters to the end of S to form a palindrome of length 2N - L. It can also be easily shown that if there exists a palindrome beginning with S that has length 2N - L, the last L characters of S must form a palindrome. Thus, to solve the problem we simply need to find the largest L such that the last L characters of S form a palindrome. To do this we simply perform a loop to check each possibility, as shown in the solution below:

#include <cstdio>
using namespace std;

FILE *fin = fopen ("shortpal.in", "r");
FILE *fout = fopen ("shortpal.out", "w");

const int MAXN = 1005;

int N;
char cows [MAXN];

/* checks if the substring beginning at 'start' is a palindrome */
bool palin (int start)
{
    for (int end = N - 1; start < end; start++, end--)
        if (cows [start] != cows [end])
            return false;

    return true;
}

int main ()
{
    fscanf (fin, "%d\n", &N);

    for (int i = 0; i < N; i++)
        fscanf (fin, "%c\n", cows + i);

    int first = -1;

/* find the first starting position that gives a palindrome */
    for (int i = 0; i < N && first == -1; i++)
        if (palin (i))
            first = i;

    fprintf (fout, "%d\n", N + first);

/* print the original string */
    for (int i = 0; i < N; i++)
        fprintf (fout, "%c\n", cows [i]);

/* print the reverse of the substring */
    for (int i = first - 1; i >= 0; i--)
        fprintf (fout, "%c\n", cows [i]);

    return 0;
}