一，题意：
给出一组字典的单词，以’#’结束，之后给出一组要执行模糊匹配的单词序列，以’#’结束
1，若某个单词能在字典中找到，则输出corret
2，若某个单词能通过 变换 或 删除 或 添加一个字符后，在字典中找得到，则输出这些单词，输出顺序根据输入的那部字典的字典序
3，若某个单词无论操作与否都无法在字典中找得到，则输出空
二，思路：
暴力模拟。
1，输入，以’#’结束
2，判断字典的单词和被匹配的单词的长度
i，如果word的长度等于dict的长度，则可能两个字符串匹配，也可能通过修改其中一个字符之后相匹配。
ii，否则如果word的长度比dict的长度大 1 ，则判断通过删除一个字符后是否相匹配。
iii，否则如果dict的长度等于word的长度大 1 ，则判断通过添加一个字符后是否相匹配。
3，输出。
三，步骤：
1，输入。
2，判断：
i，if strlen(word[])==strlen(dict[])
if !strcmp(word[i], dict[j]) , 输出corret.
else if 它们之间不同的字符个数 <= 1 , 则把单词的数组下标存入ans[]
ii，else if strlen(word[])- strlen(dict[]) == 1
if 它们之间不同的字符个数 <= 1 , 则 把单词的数组下标存入ans[]
iii，else if strlen(dict[]) – strlen(word[] == 1
if 它们之间不同的字符个数 <= 1 , 则 把单词的数组下标存入ans[]
3，输出。
#include<iostream>
#include<cstring>
using namespace std; char dict[][]; //存储字典
char word[][]; //存储要匹配的单词
int dictNum = ; //字典中单词的个数
int wordNum = ; //要被匹配的单词的个数
int dictLen[]; //存储每个单词的长度
int ans[]; //存储每个单词在字典中的位置 //变换一个字符是否相同
bool change(char word[], char dict[]) {
int count = ;
for (int i = ; i < strlen(word); i++) {
if (word[i] != dict[i]) {
count++;
if (count > ) { //不同的字母不超过1个
return false;
}
}
}
return true;
} //删除一个字符是否相同
bool del(char word[], char dict[]) {
int count = ;
for (int i = , j = ; i < strlen(word); i++) { //word的长度>dict的长度
if (word[i] != dict[j]) { //如果不等于,word[]向后移一位
count++;
if (count > ) {
return false;
}
}
else { //否则word[],dict[]都往后移一位
j++;
}
}
return true;
} //添加一个字符是否相同
bool add(char word[], char dict[]) {
int count = ;
for (int i = , j = ; i < strlen(dict); j++) { //dict的长度>word的长度
if (word[i] != dict[j]) { //如果不等于,dict[]向后移一位
count++;
if (count > ) {
return false;
}
}
else { //否则word[],dict[]都往后移一位
i++;
}
}
return true;
} //主要工作
void work(char dict[][], char word[][]) {
for (int i = ; i < dictNum; i++) {
dictLen[i] = strlen(dict[i]);
}
for (int i = ; i < wordNum; i++) {
memset(ans, , sizeof(ans));
int len = strlen(word[i]);
bool flag = false; //标记区分是第几种情况
int k = ;
for (int j = ; j < dictNum; j++) {
if (dictLen[j] == len) { //Change or Equal
if (!strcmp(word[i], dict[j])) {
flag = true; //若满足第一种情况，则为真
break;
}
else if (change(word[i], dict[j])) {
ans[k++] = j; //如果相同ans[]存储单词在字典中的位置
}
}
else if (len - dictLen[j] == ) { //Delete
if (del(word[i], dict[j])) {
ans[k++] = j;
}
}
else if (dictLen[j] - len == ) { //Add
if (add(word[i], dict[j])) {
ans[k++] = j;
}
}
}
if (flag) {
cout << word[i] << " is correct" << endl;
}
else {
cout << word[i] << ": ";
for (int j = ; j < k; j++) {
cout << dict[ans[j]] << ' ';
}
cout << endl;
}
}
} int main() {
//输入，以'#'结束
while (cin >> dict[dictNum] && dict[dictNum++][] != '#');
while (cin >> word[wordNum] && word[wordNum++][] != '#');
dictNum--; //存储时，不存'#'
wordNum--;
work(dict, word);
return ;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。
