USACO 1.3 Calf Flac


直接暴力法,对每一个字母字符,向左向右略过所有非字母字符,判断遇到的两个字母是否相等,相等则更新一下以i为中心的回文串的最大长度。
回文串长度可能是奇数也可能是偶数,扫描两次即可。时间复杂度为O(2*10^4*10^3*2)

#include <iostream>
#include 
<fstream>

using namespace std;

ifstream fin(
"calfflac.in");
ofstream fout(
"calfflac.out");

#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif

char text[20000];

void solve()
{
    
int text_len = 0;
    
char ch;
    
whilein.get(ch) ){
         text[text_len
++= ch;
    }

    
int s,e;
    
int len;
    s 
= e = len = 0;

    
//对每一个i,计算以i为中心的最长的回文
    for(int i=0;i<text_len;++i){

        
if(!isalpha(text[i]) )
            
continue;

        
int pal_s,pal_e;
        pal_s 
= i+1;
        pal_e 
= i;

        
int pal_len = 0;

        
while(true){
                pal_s
--;
                pal_e
++;
            
while(pal_s>=0&&!isalpha(text[pal_s])){
                    pal_s
--;
            }

            
while(pal_e<text_len&&!isalpha(text[pal_e])){
                    pal_e
++;
            }

            
if(pal_s>=0&&pal_e<text_len&&toupper(text[pal_s])==toupper(text[pal_e])){
                pal_len
+=2;
                
if(pal_len>len){
                    len 
= pal_len; 
                    s 
= pal_s;
                    e 
= pal_e;
                }
            }
else{
                
break;
            }
        }

        pal_s 
= i;
        pal_e 
= i;
        pal_len 
= 1;
        
         
while(true){

            pal_s
--;
            pal_e
++;

            
while(pal_s>=0&&!isalpha(text[pal_s])){
                    pal_s
--;
            }

            
while(pal_e<text_len&&!isalpha(text[pal_e])){
                    pal_e
++;
            }

            
if(pal_s>=0&&pal_e<text_len&&toupper(text[pal_s])==toupper(text[pal_e])){
                pal_len
+=2;
                
if((pal_len)>len){
                    len 
= pal_len; 
                    s 
= pal_s;
                    e 
= pal_e;
                }
            }
else{
                
break;
            }
        }
   }

    
out<<len<<endl;
    
for(int i=s;i<=e;++i)
        
out.put(text[i]);
    
out<<endl;
}

int main(int argc,char *argv[])
{
  solve();
  
return 0;
}


posted on 2009-06-06 16:03 YZY 阅读(1614) 评论(0)  编辑 收藏 引用 所属分类: AlgorithmUSACO


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


导航

<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

统计

常用链接

留言簿(2)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜