回文串不考虑除字母以外的字符,并且不区分大小写。strupr()usaco不让用,可能toupper可以。strcat(s1,s2)中s1必须为数组才可以不报错。while(fgets(line,100,fin)!=NULL)读入的一行包括结尾的换行符。注意处理大小写情况。第一种方法在usaco的test8中超时了。第二种,网上查的DP方法,讨论奇偶性,高效简单快捷。
(1)暴搜。每读入一行,从此行的第一个字符起依次作为回文串的末尾判断比较。
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cctype>
![](/Images/OutliningIndicators/None.gif)
using namespace std;
#define MAX(a,b) (a)>(b)?(a):(b)
char buf[20010],line[100],file[20010],str[2010]="test";
int n=0,rmax=0,m=0;
//bool ispal(char *s1,char* s2)
//{
// strcpy(buf,s1);
// strupr(buf);
// //strupr(s2);
// while(*s1==*s2&&s2-s1>0)
// {
// s1++;
// s2--;
// while(*s1<'A'||*s1>'Z')s1++;
// while(*s2<'A'||*s2>'Z')s2--;
// }
// if(s2==s1||*s2==*s1)return 1;
// return 0;
//}
bool ispal(char *buf1,char* buf2)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int tmp=buf2-buf1+1;
if(tmp<m)//test
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return 0;
}
while(*buf1==*buf2&&buf2-buf1>0)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
buf1++;
buf2--;
if(*buf2<='z'&&*buf2>='a')*buf2-=32;
if(*buf1<='z'&&*buf1>='a')*buf1-=32;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(*buf1<'A'||*buf1>'Z')
{buf1++;n++;if(*buf1<='z'&&*buf1>='a')*buf1-=32;}
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(*buf2<'A'||*buf2>'Z')
{buf2--;n++;if(*buf2<='z'&&*buf2>='a')*buf2-=32;}
}
if(buf2==buf1||*buf2==*buf1)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
//if(tmp>m&&tmp<n)//test
// {
// tmp=5+n;
// }
return 1;
}
return 0;
}
void cal(char* s1,char* s2)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
char* buf2,*buf1;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//*while(!(*s1<='z'&&*s1>='a'||*s1<='Z'&&*s1>='A'))s1++;*/
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//*while(!isalpha(*s1))s1++;*/
strcpy(buf,s1);
//strupr(buf);
buf1=buf;
buf2=buf+(s2-s1);//
char* pt=buf1;
int t=MAX(s2-s1-2000,0);
while(t>0)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
pt++;
t--;
}
int tmp;
while(*buf2!='\0')
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(*buf2<='z'&&*buf2>='a')*buf2-=32;
pt=buf1;
while(buf2-pt>0)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if((tmp=buf2-pt+1)<m)break;
if(*pt<='z'&&*pt>='a')*pt-=32;
if(*pt==*buf2&&isalpha(*pt)&&ispal(pt,buf2))
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
//tmp=buf2-pt+1;
if(tmp>m)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
m=tmp;
strcpy(str,s1+(pt-buf1));
*(str+m)='\0';
rmax=m-n;
// if(rmax<0)//test
//{
// tmp=5+n;
//}
//
}
}
n=0;
pt++;
}
buf2++;
}
}
int main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
FILE* fin;
FILE* fout;
fin=fopen("calfflac.in","r");
fout=fopen("calfflac.out","w");
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//*fin=fopen("stdin","r");
fout=fopen("stdout","w");*/
//char* s="sda";
int i,ln=0;
int len,max=0;
char *p;
while(fgets(line,100,fin)!=NULL)
//while(fgets(line,MAX,stdin)!=NULL)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
line[strlen(line)-1]='\0';
//fprintf(stdout,"%c\n",line[strlen(line)-1]);
i=strlen(file);
strcat(file,line);
len=MAX(i-2000,0);
p=file+len;
//while(!isalpha(*p))p++;
cal(p,file+i);
//if(len>max)max=len;
}
fprintf(fout,"%d\n",rmax);
//fprintf(fout,"%s\n",str);
i=0;ln=-1;
while(*(str+i)!='\0')
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
ln++;
fprintf(fout,"%c",*(str+i));
if(ln%80==78)fprintf(fout,"\n");
i++;
}
#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
freopen("calfflac.in","r",stdin);
freopen("calfflac.out","w",stdout);
char a[20005],b[20005],c;
int ba[20005],d[20005],r=0,rpos=0;
int ai=0,bi=0;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(scanf("%c",&c)!=EOF)
{
a[ai]=c;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(c>='a'&&c<='z'||c>='A'&&c<='Z')
{
b[bi]=c;
if(c>='A'&&c<='Z')b[bi]+='a'-'A';
ba[bi]=ai;//b与a的字符对应关系
bi++;
}
ai++;
}
d[0]=1;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=1;i<bi;i++)
{
if(b[i]==b[i-d[i-1]-1])d[i]=d[i-1]+2;
else if(b[i]==b[i-1])d[i]=2;
else d[i]=1;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(d[i]>r)
{
r=d[i];
rpos=i;
}
}
printf("%d\n",r);
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=ba[rpos-r+1];i<=ba[rpos];i++)
{
printf("%c",a[i]);
}
printf("\n");
return 0;
} if(ln%80!=78)fprintf(fout,"\n");
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//*fprintf(stdout,"%d\n",rmax);
fprintf(stdout,"%s\n",str);*/
return 0;
}(2)DP。a为原数组,b为需考虑以判断回文的数组。ab为记录a中回文位置。