POJ 1035(文字列シミュレーション)

タイトルリンク:http://poj.org/problem?id=1035
題意:辞書を1つ与えて、それからいくつかの単語を与えて、変換を通じて辞書の中でその単語を見つけることができますか?
①1文字置換
②1文字削除
③1文字挿入
この単語が既に辞書にある場合は、変更する必要はありません.
変換で単語が見つからない場合は、出力する必要はありません.
考え方:
シミュレーションしましょう.データはあまり大きくありませんが、よく考えてからコードを書いてください.シミュレーション問題は硬傷です.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;

const int INF=0x3f3f3f3f;
const int maxn=10010;
char dic[maxn][100];
int cnt;

void read_Dic(){
	cnt=0;
	while(scanf("%s",dic[cnt])){
		if(dic[cnt][0]=='#')
			break;
		cnt++;
	}
}

bool isCorrect(char *str){
	for(int i=0;i<cnt;i++){
		if(strcmp(str,dic[i])==0)
			return true;
	}
	return false;
}

void Replace(char *str,char *dic){
	int diff=0;
	int dicLen=strlen(dic);
	for(int j=0;j<dicLen;j++){
		if(str[j]!=dic[j])
			diff++;
	}
	if(diff==1)
		printf(" %s",dic);
}

void Insert(char *str,char *dic){
	int arr[100];
	int len=strlen(str);
	int dicLen=strlen(dic);
	memset(arr,-1,sizeof(arr));
	for(int j=0;j<len;j++){
		for(int k=j==0?0:arr[j-1]+1;k<dicLen;k++){
			if(str[j]==dic[k]){
				arr[j]=k;
				break;
			}
		}
	}
	bool isMatch=true;
	for(int j=0;j<len;j++){
		if(arr[j]==-1){
			isMatch=false;
			break;
		}
	}
	if(isMatch) printf(" %s",dic);
}

void Delete(char *str,char *dic){
	int arr[100];
	int len=strlen(str);
	int dicLen=strlen(dic);
	memset(arr,-1,sizeof(arr));
	for(int j=0;j<dicLen;j++){
		for(int k=j==0?0:arr[j-1]+1;k<len;k++){
			if(str[k]==dic[j]){
				arr[j]=k;
				break;
			}
		}
	}
	bool isMatch=true;
	for(int j=0;j<dicLen;j++){
		if(arr[j]==-1){
			isMatch=false;
			break;
		}
	}
	if(isMatch) printf(" %s",dic);
}

void Operate_Str(char *str){
	printf("%s:",str);
	int len=strlen(str);
	for(int i=0;i<cnt;i++){
		int dicLen=strlen(dic[i]);
		if(len==dicLen){//  
			Replace(str,dic[i]);
		}
		else if(len+1==dicLen){//  
			Insert(str,dic[i]);
		}
		else if(len==dicLen+1){//  
			Delete(str,dic[i]);
		}
	}
	putchar(10);
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
#endif
	read_Dic();
	char str[100];
	while(scanf("%s",str)){
		if(str[0]=='#') break;
		if(isCorrect(str))
			printf("%s is correct
",str);
		else
			Operate_Str(str);
	}
	return 0;
}