POJ 1035文字列

辞書を1つ与えて、それから1組の単語の集合を与えて、もしその単語が辞書の中にあるならば、correctを出力します;そうでなければ、1>1文字を挿入する2>1文字を削除する3>1文字を置換する3つの操作のうちの1つを辞書順の単語に変換して出力することができます.直接暴力したことがあって、c++は过ごすことができて、g++はタイムアウトします.

//11222230	c00h00g	1035	Accepted	1200K	500MS	C++	1530B	2013-01-30 15:07:29
#include<string>
#include<iostream>
#include<map>
using namespace std;
string word[10005];
map<string,int> mp;
//         
bool check_replace(string a,string b,int len){
    int res=0;
    for(int i=0;i<len;i++)
        if(a[i]!=b[i]) res++;
    if(res==1) return true;
    return false;
}
//            ，    ，             
bool check_insert(string a,string b,int len1,int len2){
    int i=0,j=0;
    while(i<len1&&j<len2&&a[i]==b[j]){i++;j++;}
    j++;//b         
    while(i<len1&&j<len2&&a[i]==b[j]){i++;j++;}
    if(i==len1&&j==len2) return true;
    return false; 
}
int main(){
    int i=0;
    while(cin>>word[i]&&word[i]!="#"){
        mp[word[i]]=1;
        i++;
    }
    int n=i;
    string test;
    while(cin>>test&&test!="#"){
        if(mp[test])
            cout<<test<<" is correct"<<endl;
        else{
           cout<<test<<":";
           int len1=test.length();
           for(int i=0;i<n;i++){
               int len2=word[i].length();
               if(len1==len2){
                   if(check_replace(test,word[i],len1))
                       cout<<" "<<word[i];
               }else if(len1+1==len2){//insert a char
                   if(check_insert(test,word[i],len1,len2))
                       cout<<" "<<word[i];
               }else if(len1-1==len2){//delete a char
                   if(check_insert(word[i],test,len2,len1))
                       cout<<" "<<word[i];
               }
           }
           cout<<endl;
        }        
    }
    return 0;
}