1412: 1.3.3 Calf Flac

题目描述

据说如果你给无限只母牛和无限台巨型便携式电脑(有非常大的键盘),那么母牛们会制造出世上最棒的回文。你的工作就是去寻找这些牛制造的奇观(最棒的回文)。

在寻找回文时不用理睬那些标点符号、空格(但应该保留下来以便做为答案输出),只用考虑字母'A'-'Z'和'a'-'z'。要你寻找的最长的回文的文章是一个不超过20,000个字符的字符串。

我们将保证最长的回文不会超过2,000个字符(在除去标点符号、空格之前)。

输入

输入文件不会超过20,000字符。这个文件可能一行或多行，但是每行都不超过80个字符(不包括最后的换行符)。

输出

输出的第一行应该包括找到的最长的回文的长度。

下一行或几行应该包括这个回文的原文（没有除去标点符号、空格），把这个回文输出到一行或多行（如果回文中包括换行符）。

如果有多个回文长度都等于最大值，输出最前面出现的那一个。

样例输入

Confucius say: Madam, I'm Adam.

样例输出

11
Madam, I'm Adam

参考代码

#include <stdio.h>
#include <string.h>
//#include <time.h>
struct 
{
    int start;
    int end;
    int length;
}
f;
char str[20015],a[20015];
int b[20015];
int main() 
{
    int i=0,j=0,s,t;
    //    long l1,l2;
    //int k;
    while(scanf("%c",&str[i])!=EOF) 
    {
        if(str[i]>='a' && str[i]<='z') 
        {
            a[j]=str[i];
            b[j++]=i;
        }
        if(str[i]>='A' && str[i]<='Z') 
        {
            a[j]=str[i]+32;
            b[j++]=i;
        }
        i++;
    }
    //    l1=clock();
    /*    for(i=0;i<j;i++){
        for(k=i+1;k<j;k++)
            if(a[k]==a[i]){
                t=k-1;
                for(s=i+1;s<=i+(k-i)/2;){
                    if(a[s]!=a[t])
                        break;
                    s++;
                    t--;
                }
                if(s>i+(k-i)/2 && f.length<(k-i+1)){
                    f.start=b[i];
                    f.end=b[k];
                    f.length=k-i+1;
                }
            }
    }*/
    //这种方法每一个字母a[i]对应后面的字母a[t]都从i+1个字母开始到结尾j，
    //如果a[t]==a[i]就从两端到中间寻找、判断是否为回文
    //缺点：太浪费时间
    /***********改正后*************/
    //从同学处请教到节约时间的算法，就是每个字母a[i]都出发到两端去*/
    for (i=0;i<j-1;i++) 
    {
        if(a[i]==a[i+1]) 
        {
            //偶数个
            if(i==0) 
            {
                f.start=b[i];
                f.end=b[i+1];
                f.length=2;
            } else 
            {
                for (s=i-1,t=i+2;s>=0 && t<j;s--,t++) 
                {
                    if(a[s]!=a[t])
                                            break;
                }
                if(t-s-1>f.length) 
                {
                    f.start=b[s+1];
                    f.end=b[t-1];
                    f.length=t-s-1;
                }
            }
        }
        //奇数个
        for (s=i-1,t=i+1;s>=0 && t<j;s--,t++) 
        {
            if(a[s]!=a[t])
                            break;
        }
        if(t-s-1>f.length) 
        {
            f.start=b[s+1];
            f.end=b[t-1];
            f.length=t-s-1;
        }
    }
    if(!f.length) 
    {
        printf("1n%c",a[0]);
        return 0;
    }
    //    l2=clock();
    //    printf("%ldmsn",l2-l1);
    printf("%dn",f.length);
    for(i=f.start;i<=f.end;i++)
        printf("%c",str[i]);
    return 0;
}/*11
 Confucius say: Madam, I'm Adam.
Madam, I'm Adam*/

解析

暂无