PKU 1035 Spell checker
http://poj.org/problem?id=1035
辞書としての文字列とスペルチェックをする文字列が与えられる。
辞書としての文字列にスペルチェックするべき文字列が含まれていればその文字列は正しい。
そうでない場合、以下の条件のいずれかを満たす辞書文字列を表示する。
・文字列に何か文字を付け加えたものが辞書に存在する。
・文字列から1文字取り除いたものが辞書に存在する。
・文字列を1文字入れ替えたものが辞書に存在する。
だいたいこんな感じの問題。
最初これよりも愚直に書いてTLEったので、多少書き換えて高速化しました。
微妙にほとんど同じコードが紛れているのが若干悲しいです。
main(){ map<int,string> app; set<string> sapp; string dir; int num=0; while(cin>>dir){ if(dir=="#")break; app[num++]=dir; sapp.insert(dir); } string in; while(cin>>in){ if(in=="#")break; if(sapp.count(in))cout<<in<<" is correct"<<endl; else{ cout<<in<<':'; FOR(miter,app){ const string& ss=miter->S; if(abs(int(in.size())-int(ss.size()))>1)continue; bool ok=false; if(in.size()==ss.size()){ int diff=0; rep(i,in.size()) if(in[i]!=ss[i]){ ++diff; if(diff>2)break; } if(diff==1)ok=true; }else if(in.size()<ss.size()){ rep(i,ss.size()){ int p=0; bool tok=true; rep(j,in.size()){ if(p==i)++p; if(ss[p]!=in[j]){ tok=false; break; } ++p; } if(tok){ ok=true; break; } } }else{ rep(i,in.size()){ int p=0; bool tok=true; rep(j,ss.size()){ if(p==i)++p; if(in[p]!=ss[j]){ tok=false; break; } ++p; } if(tok){ ok=true; break; } } } if(ok)cout<<' '<<miter->S; } cout<<endl; } } }