Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/529-65f468fb
この記事にトラックバックする(FC2ブログユーザー)

Aizu 1203 - Napoleon's Grumble (この記事を編集する[管理者用])

Source

ACM/ICPC Tokyo 1998
UVa 689
ZJU 1660
Aizu 1203

問題概要

1024文字以下の文字列が与えられる.アルファベット以外は無視し,アルファベットは全て大文字に変換する.
その文字列の長さ3以上の部分文字列で極大の回文となっているものを全て出力する問題.
ただし,極大の回文という意味は,文字列Xが回文で,ある文字cに対してcXcという文字列も部分文字列に含まれるならXは出力しないという意味.
Aizuでは出力する順番は任意,UVaとZJUでは辞書順に出力しなければいけない.

解法

中心を決め打って,答えの候補を全部列挙する.
後は,それが他の中心の回文に含まれなければ出力するとかそんな感じで適当にやる.
O(n^3)の気もするけど通る.(n=文字列の長さ)

記事更新履歴 (2009-08-28 01:50)

ソースにZJUへのリンクを追加.
ZJUに関する仕様追記.(UVaでは→UVaとZJUでは)

C言語のスパゲッティなコード (Aizu用)
#include<stdio.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int is_same(char a[],char b[],int len){ int i; rep(i,len)if(a[i]!=b[i])return 0; return 1; }

int main(){
  int i,j,k,l,m,n,len;
  int cnv[260];
  char in[20000];
  int go[2000], fg, add, st, ed, dame;

  rep(i,260) cnv[i]=0; rep(i,26) cnv['a'+i]=cnv['A'+i]='A'+i;
  while(fgets(in,20000,stdin)){
    fg=len=0;
    for(i=0;;i++){
      if(in[i]<' ') break;
      if(cnv[in[i]]) in[len++]=cnv[in[i]];
    }
    rep(add,2){
      rep(i,len-add){
        st=i; ed=i+add;
        for(k=0;;k++){
          if(st-k<0 || ed+k>=len) break;
          if(in[st-k]!=in[ed+k]) break;
        }
        go[i]=k;
      }
      rep(i,len-add) if(go[i]>=2){
        dame=0;
        rep(j,len-add){
          if(go[j]<go[i]) continue;
          if(go[j]==go[i] && j>=i) continue;
          if(is_same(in+i-go[i]+1,in+j-go[i]+1,go[i]*2-1+add)){ dame=1; break; }
        }
        if(!dame){
          if(fg) putchar(' '); else fg=1;
          rep(k,go[i]*2-1+add) putchar(in[i-go[i]+1+k]);
        }
      }
    }
    puts("");
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/529-65f468fb
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。