1035-Spell checker(模糊匹配)，1035-spellchecker
一，題意：
給出一組字典的單詞，以'#'結束，之後給出一組要執行模糊匹配的單詞序列，以'#'結束
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 #include<iostream>
2 #include<cstring>
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 }
View Code
版權聲明：本文為博主原創文章，未經博主允許不得轉載。
