1035spellchecker.cpp

算法编程题,北京大学OnlineJudge 1035Spellchecker

#include<stdio.h>  
#include<math.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<vector>
#include<set>
#include<map>
using namespace std;

//字符串匹配,暴力

int dicN;
int dicLen[10001];
char dic[10001][16];
char bf[100];

bool Input(){
	int i;
	dicN=0;
	if(scanf("%s",&dic[dicN])==EOF){
		return 0;
	}
	dicN++;
	while(1){
		scanf("%s",&dic[dicN]);
		if(dic[dicN][0]=='#'){
			break;
		}
		dicN++;
	}
	for(i=0;i<dicN;i++){
		dicLen[i]=strlen(dic[i]);
	}
	return 1;
}

bool Check(char s1[],char s2[]){
	int len1=strlen(s1);
	int len2=strlen(s2);
	int i,j,k;
	if(len1==len2){
		for(j=0,i=0;i<len1;i++){
			if(s1[i]!=s2[i]){
				j++;
			}
		}
		return j==1;
	}else if(len1+1==len2){
		for(i=0;i<len1;i++){
			if(s1[i]!=s2[i]) break;
		}
		for(;i<len1;i++){
			if(s1[i]!=s2[i+1]){
				return 0;
			}
		}
		return 1;
	}else if(len1-1==len2){
		for(i=0;i<len2;i++){
			if(s1[i]!=s2[i]) break;
		}
		for(;i<len2;i++){
			if(s1[i+1]!=s2[i]){
				return 0;
			}
		}
		return 1;
	}
	return 0;
}

void Proc(char s[]){
	int i,j,k;
	int sLen=strlen(s);
	//correct
	for(i=0;i<dicN;i++){
		if(sLen==dicLen[i]&&strcmp(s,dic[i])==0){
			printf("%s is correct\n",s);
			return;
		}
	}
	//replace
	printf("%s:",s);
	for(i=0;i<dicN;i++){
		if(Check(s,dic[i])){
			printf(" %s",dic[i]);
		}
	}
	printf("\n");
	return;
}

void Solve(){
	int i,j,k;
	while(1){
		scanf("%s",&bf);
		if(bf[0]=='#'){
			break;
		}
		Proc(bf);
	}
	return;
}

int main()
{
	//freopen("in.txt","r",stdin);
	while(Input()){
		Solve();
	}
	return 0;
}