希望的海洋

Ain't about how fast I get there,ain't about what's waiting on the other side

常用链接

统计

最新评论

usaco_calflac多行文件中找出最长回文串

回文串不考虑除字母以外的字符,并且不区分大小写。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>

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)
{
    
    
int tmp=buf2-buf1+1;
        
if(tmp<m)//test
                    {
                        
return 0;
                    }

    
while(*buf1==*buf2&&buf2-buf1>0)
    
{
        buf1
++;
        buf2
--;
        
if(*buf2<='z'&&*buf2>='a')*buf2-=32;
        
if(*buf1<='z'&&*buf1>='a')*buf1-=32;
        
while(*buf1<'A'||*buf1>'Z'){buf1++;n++;if(*buf1<='z'&&*buf1>='a')*buf1-=32;}
        
while(*buf2<'A'||*buf2>'Z'){buf2--;n++;if(*buf2<='z'&&*buf2>='a')*buf2-=32;}
    }

    
if(buf2==buf1||*buf2==*buf1)
    
{
        
//if(tmp>m&&tmp<n)//test
        
//            {
        
//                tmp=5+n;
        
//            }
        return 1;
    }

    
    
return 0;
}

void cal(char* s1,char* s2)
{
    
char* buf2,*buf1;
    
/*while(!(*s1<='z'&&*s1>='a'||*s1<='Z'&&*s1>='A'))s1++;*/
    
/*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)
    
{
        pt
++;
        t
--;
    }

    
int tmp;
    
while(*buf2!='\0')
    
{
        
if(*buf2<='z'&&*buf2>='a')*buf2-=32;
        pt
=buf1;
        
while(buf2-pt>0)
        
{
            
if((tmp=buf2-pt+1)<m)break;
            
if(*pt<='z'&&*pt>='a')*pt-=32;
            
if(*pt==*buf2&&isalpha(*pt)&&ispal(pt,buf2))
            
{
                    
//tmp=buf2-pt+1;
                    
                    
if(tmp>m)
                        
{
                            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()
    
{
        FILE
* fin;
        FILE
* fout;
        fin
=fopen("calfflac.in","r");
        fout
=fopen("calfflac.out","w");
        
/*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)
        {
            
            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')
            
{
                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; 
 
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
    
while(scanf("%c",&c)!=EOF)
         a[ai]
=c; 
         
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
    
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
        
if(d[i]>r)
             r
=d[i]; 
             rpos
=i; 
         }
  
    }
 
    printf(
"%d\n",r); 
     
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");
        
/*fprintf(stdout,"%d\n",rmax);
        fprintf(stdout,"%s\n",str);
*/

        
return 0;
}
(2)DP。a为原数组,b为需考虑以判断回文的数组。ab为记录a中回文位置。



posted on 2011-08-11 11:23 拥梦的小鱼 阅读(430) 评论(0)  编辑 收藏 引用 所属分类: USACO


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理