POJ 1035 Spell Checker

想法：

• dic[i],check字數相等的情況
• dic[i],check字數相差1的情況

	#include <cstdio>
	using namespace std;
	struct dictionary
	{
	char l[20];
	int num;
	}dic[10002];
	int main()
	{
	char check[20];
	int i,j,k;
	for(i=0;;i++){
	scanf("%s",dic[i].l);
	if(dic[i].l[0]=='#') break;
	for(dic[i].num=0;dic[i].l[dic[i].num];dic[i].num++); //計算字元數
	}
	int numOfdic=i;
	while(1){
	scanf("%s",check);
	if(check[0]=='#') break;
	int nOfcheck=0;
	for(;check[nOfcheck];nOfcheck++);
	int diff=0,same=0; //same=1表示完全正確
	char *correct[10002]; int nOfcorrect=0;
	for(i=0,diff=0,same=0;i<numOfdic;i++,diff=0){
	if (nOfcheck-dic[i].num>1 || nOfcheck-dic[i].num<-1) continue;
	else if(nOfcheck==dic[i].num){ //字數相等的情況
	for(j=0;check[j];j++)
	if(check[j]!=dic[i].l[j])
	diff++;
	if (diff==0){
	same=1;
	printf("%s is correct\n",check);
	break;
	}
	else if(diff==1) correct[nOfcorrect++]=&dic[i].l[0];
	}
	else{ //字數相差1的情況
	int d_i=0,c_i=0; //dic_index,check_index
	while(dic[i].l[d_i] && check[c_i]){
	if(dic[i].l[d_i]==check[c_i]){d_i++; c_i++;}
	else{
	diff++;
	if(diff>1) break;
	if(nOfcheck>dic[i].num) c_i++;
	else d_i++;
	}
	}
	if(diff<=1) correct[nOfcorrect++]=&dic[i].l[0];
	}
	}
	if(!same){
	printf("%s:",check);
	for(j=0;j<nOfcorrect;j++)
	printf(" %s",correct[j]);
	printf("\n");
	}
	}
	return 0;
	}

view raw [POJ] 1035 Spell Checker.cpp hosted with ❤ by GitHub