一，题意：
给出一组字典的单词，以'#'结束，之后给出一组要执行模糊匹配的单词序列，以'#'结束 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，输出。
1 #include2 #include 3 using namespace std; 4 5 char dict[10001][16]; //存储字典 6 char word[51][16]; //存储要匹配的单词 7 int dictNum = 0; //字典中单词的个数 8 int wordNum = 0; //要被匹配的单词的个数 9 int dictLen[10001]; //存储每个单词的长度 10 int ans[10001]; //存储每个单词在字典中的位置 11 12 //变换一个字符是否相同 13 bool change(char word[], char dict[]) { 14 int count = 0; 15 for (int i = 0; i < strlen(word); i++) { 16 if (word[i] != dict[i]) { 17 count++; 18 if (count > 1) { //不同的字母不超过1个 19 return false; 20 } 21 } 22 } 23 return true; 24 } 25 26 //删除一个字符是否相同 27 bool del(char word[], char dict[]) { 28 int count = 0; 29 for (int i = 0, j = 0; i < strlen(word); i++) { //word的长度>dict的长度 30 if (word[i] != dict[j]) { //如果不等于,word[]向后移一位 31 count++; 32 if (count > 1) { 33 return false; 34 } 35 } 36 else { //否则word[],dict[]都往后移一位 37 j++; 38 } 39 } 40 return true; 41 } 42 43 //添加一个字符是否相同 44 bool add(char word[], char dict[]) { 45 int count = 0; 46 for (int i = 0, j = 0; i < strlen(dict); j++) { //dict的长度>word的长度 47 if (word[i] != dict[j]) { //如果不等于,dict[]向后移一位 48 count++; 49 if (count > 1) { 50 return false; 51 } 52 } 53 else { //否则word[],dict[]都往后移一位 54 i++; 55 } 56 } 57 return true; 58 } 59 60 //主要工作 61 void work(char dict[][16], char word[][16]) { 62 for (int i = 0; i < dictNum; i++) { 63 dictLen[i] = strlen(dict[i]); 64 } 65 for (int i = 0; i < wordNum; i++) { 66 memset(ans, 0, sizeof(ans)); 67 int len = strlen(word[i]); 68 bool flag = false; //标记区分是第几种情况 69 int k = 0; 70 for (int j = 0; j < dictNum; j++) { 71 if (dictLen[j] == len) { //Change or Equal 72 if (!strcmp(word[i], dict[j])) { 73 flag = true; //若满足第一种情况，则为真 74 break; 75 } 76 else if (change(word[i], dict[j])) { 77 ans[k++] = j; //如果相同ans[]存储单词在字典中的位置 78 } 79 } 80 else if (len - dictLen[j] == 1) { //Delete 81 if (del(word[i], dict[j])) { 82 ans[k++] = j; 83 } 84 } 85 else if (dictLen[j] - len == 1) { //Add 86 if (add(word[i], dict[j])) { 87 ans[k++] = j; 88 } 89 } 90 } 91 if (flag) { 92 cout << word[i] << " is correct" << endl; 93 } 94 else { 95 cout << word[i] << ": "; 96 for (int j = 0; j < k; j++) { 97 cout << dict[ans[j]] << ' '; 98 } 99 cout << endl;100 }101 }102 }103 104 int main() {105 //输入，以'#'结束106 while (cin >> dict[dictNum] && dict[dictNum++][0] != '#');107 while (cin >> word[wordNum] && word[wordNum++][0] != '#');108 dictNum--; //存储时，不存'#'109 wordNum--;110 work(dict, word);111 return 0;112 }
版权声明：本文为博主原创文章，未经博主允许不得转载。