PKU 2934 Automatic Correction of Misspellings
http://poj.org/problem?id=2934
n個の辞書文字列が与えられる。
ここでq個の文字列のクエリが与えられるので、その文字列に対して
・辞書に含まれていればそのことを出力。
・そうでなければ以下の3つの条件のうちどれかを満たしていればそのことを出力。
1.辞書文字列に対して1文字多いか少ない。
2.辞書文字列と一文字だけ違っている。
3.クエリ文字列の隣接する文字を交換すると辞書文字列に一致する。
・上の二つの条件に合わなければそのことを出力。
という操作を行うというような問題。
http://poj.org/userstatus?user_id=semingo
やたらと難しい問題ばかりを解いているっぽいこの人の解いた問題で、
回答者数がそれほど多くなくて、自分でも解けそうな問題という理由で選択。
辞書文字列をハッシュで持つ必要があると思います。
あとはクエリ文字列に操作をして探しました。
typedef struct _node{ int idx; _node *next; }node; const int hashMod=100007; node *hash[hashMod]; node ent[10000]; int sz; char in[10000][30]; void insert(int idx){ int ha=0; for(char *p=in[idx];*p;++p) ha=(ha*37+*p)%hashMod; node *p=ent+sz++; p->idx=idx; p->next=hash[ha]; hash[ha]=p; } int mystrcmp(char *a,char *b,int idx=-1,char ch='\0'){ int idxa=0,idxb=0; char ac,bc; do{ if(a[idxa]=='a'-1)++idxa; if(b[idxb]=='a'-1)++idxb; ac=a[idxa]; if(idx==-1 || idxb<idx)bc=b[idxb]; else if(idxb==idx)bc=ch; else if(idxb>idx)bc=b[idxb-1]; if(ac-bc)return ac-bc; ++idxa; ++idxb; }while(ac && bc); return ac-bc; } int count(char *str,int idx=-1,char ch='\0'){ int ha=0; for(int i=0;str[i];++i){ if(str[i]=='a'-1)continue; if(i==idx)ha=(ha*37+ch)%hashMod; ha=(ha*37+str[i])%hashMod; } if(idx!=-1 && !str[idx]) ha=(ha*37+ch)%hashMod; int ret=100000; for(node*p=hash[ha];p;p=p->next) if(mystrcmp(in[p->idx],str,idx,ch)==0) ret=min(ret,p->idx); return ret; } char str[30]; main(){ int n; scanf("%d",&n); rep(i,n){ scanf("%s",in[i]); insert(i); } int q; scanf("%d",&q); while(q--){ memset(str,0,sizeof(str)); scanf("%s",str); if(count(str)<n){ printf("%s is correct\n",str); continue; } int pr=n; for(int i=1;str[i];++i){ swap(str[i-1],str[i]); pr=min(count(str),pr); swap(str[i-1],str[i]); } for(int i=0;str[i];++i){ char ba=str[i]; rep(j,27){ str[i]='a'+j-1; pr=min(count(str),pr); } str[i]=ba; } for(int i=0;i==0 || str[i-1];++i) for(char ch='a';ch<='z';++ch) pr=min(count(str,i,ch),pr); if(pr<n)printf("%s is a misspelling of %s\n",str,in[pr]); else printf("%s is unknown\n",str); } }