1.3 Calf Flac

Calf Flac

To make the programming easier, we keep two copies of the text: the original, and one with the punctuation stripped out. We find the biggest palindrome in the latter copy, and then figure out which part of the original it corresponds to.

To find the biggest palindrome in the alphabetic text, we look, for each letter in the text, at the biggest palindrome centered on that letter (in the case of an odd length palindrome) or just to the right of that letter (in the case of an even length palindrome).

There are 20,000 letters, and we are assured that no palindrome is more than 2,000 letters long, and we search for both even and odd palindromes, for a total of about 20,000*2,000*2 = 80,000,000 operations, which is perfectly reasonable within the time limit.

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

char fulltext[21000];
char text[21000];

char *pal;
int pallen;

void
findpal(void)
{
    char *p, *fwd, *bkwd, *etext;
    int len;

    etext = text+strlen(text);
    for(p=text; *p; p++) {
	/* try palindrome with *p as center character */
	for(fwd=bkwd=p; bkwd >= text && fwd < etext && *fwd == *bkwd;
				fwd++, bkwd--)
			;
	bkwd++;
	len = fwd - bkwd;
	if(len > pallen) {
	    pal = bkwd;
	    pallen = len;
	}

	/* try palindrome with *p as left middle character */
	for(bkwd=p, fwd=p+1;
	          bkwd >= text && fwd < etext && *fwd == *bkwd; fwd++, bkwd--)
			;
	bkwd++;
	len = fwd - bkwd;
	if(len > pallen) {
	    pal = bkwd;
	    pallen = len;
	}
    }
}

void
main(void)
{
    FILE *fin, *fout;
    char *p, *q;
    int c, i, n;

    fin = fopen("calfflac.in", "r");
    fout = fopen("calfflac.out", "w");
    assert(fin != NULL && fout != NULL);

    /* fill fulltext with input, text with just the letters */
    p=fulltext;
    q=text;
    while((c = getc(fin)) != EOF) {
	if(isalpha(c))
	    *q++ = tolower(c);
	*p++ = c;
    }
    *p = '\0';
    *q = '\0';

    findpal();

    fprintf(fout, "%d\n", pallen);

    /* find the string we found in the original text
       by finding the nth character */
	n = pal - text;
    for(i=0, p=fulltext; *p; p++)
	if(isalpha(*p))
	    if(i++ == n)
		break;
    assert(*p != '\0');

    /* print out the next pallen characters */
    for(i=0; i<pallen && *p; p++) {
	fputc(*p, fout);
	if(isalpha(*p))
	    i++;
    }
    fprintf(fout, "\n");

    exit(0);
}

此题如果能够想到暴力，那么此题容易错的地方就在读入上，要记得是以文件结束符EOF结束输入的，而不是以'\n',因为这个原因而WA了几次。

附我的代码：

/*
ID: xxfz014
PROG: calfflac
LANG: C++
*/
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 20010;
char org[maxn];
struct node
{
    int index;
    char ch;
};
node  s[maxn];
int len;

bool isword(char c)
{
    if((c>='A'&&c<='Z')||(c>='a'&&c<='z'))  return true;
    return false;
}
int main()
{
    freopen("calfflac.in","r",stdin);
    freopen("calfflac.out","w",stdout);

    int i=0,len=0;

    while(scanf("%c",&org[len++])!=EOF);
    //printf("%d\n",len);
    //puts(org);
    for(int j=0;j<len;j++)
    {
        if(isword(org[j]))
        {
            if(org[j]>='A'&&org[j]<='Z')    s[i].ch=org[j]-'A'+'a';
            else    s[i].ch=org[j];
            s[i++].index=j;
        }
    }
    len=i;
    int maxv=0,left,right;
    for(i=0;i<len;i++)
    {
        int v=0,a=i,b=i;
        //偶数
        for(int r=i,l=i-1;r>=0&&l>=0&&r<len&&l<len;r++,l--)
        {
            if(s[r].ch==s[l].ch)    {v+=2;a=l;b=r;}
            else    break;
        }
        if(v>maxv)  {maxv=v;right=b;left=a;}
        //奇数
        v=1,a=i,b=i;
        for(int r=i+1,l=i-1;r>=0&&l>=0&&r<len&&l<len;r++,l--)
        {
            if(s[r].ch==s[l].ch)    {v+=2;a=l;b=r;}
            else    break;
        }
        if(v>maxv)  {maxv=v;right=b;left=a;}
    }
    printf("%d\n",maxv);
    for(i=s[left].index;i<=s[right].index;i++) printf("%c",org[i]);
    printf("\n");
    return 0;
}