b046. E. 智慧型單字查詢＠Morris' Blog｜PChome Online 個人新聞台

2011-08-22 19:11:23| 人氣2,066| 回應0 | 上一篇 | 下一篇

b046. E. 智慧型單字查詢

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

小批為了增加自己的英文能力，找來了一本單字書打算好好的來背單字。可是單字書上的單字真的太多了，硬背的教果實在不太好。學校的英文老師這時教了用字首字根拆解來認識英文單字的方法。

字首包括im, ab等等。顧名思義，一定是在單字的開頭。im和ab這兩個字首都有否定的意思。因此一個字加上這個字首，意思可能會反過來。例如normal是正常的意思，abnormal則是不正常。possible是可能的意思，而impossible則是不可能的意思。

而字根則可以提供這個字是在說什麼的線索，字根則可能出現在字首或是字的中間。例如fid這個字根是faith (信心)的意思。confidence可以拆成con – fid – ence來看，con表示加強語氣，所以這個字是很有信心，也就是有自信的意思。若是diffidence，因為di也是否定的字首，因此這個字是沒有信心，也就是缺乏自信的意思。

字尾例如上面例字尾的ble, ence都是。顧名思義，一定出現在單字結尾。可以讓我們看到字就知道字的詞性、類別等等。

為了應用這些老師教的概念，你決定寫一個字首字根和字尾的查詢機。輸入許多單字和查詢，請將符合規則的字都找出來。基本查詢條件如以下三種，分別用以查詢字首、字根以及字尾：

im* 表示找出所有im開頭的字。

*fid* 表示找出所有以fid開頭，結尾或是在單字中間出現fid的字，

*ence表示找出所有ence結尾的字。

查詢條件中至少會出現一個英文字母。另外為了找出同時具有特定字首字根字尾的字，語法也接受以AND合併多個條件的查詢：將多個條件寫在同一行並以一個空白字元隔開。例如：

im* *ence表示找出im開頭而且ence結尾的字。

(註：不用考慮將多個條件OR合併的情形。)

輸入說明：

輸入檔前半部包含一部字典。第一行有一個整數N (1 ≤ N ≤ 1000)，代表一共有N個單字。接下來N行，每一行有一個小寫英文單字。輸入檔的後半部有數個查詢。後半部第一行有一個整數M (1 ≤ M ≤ 1000)，代表一共有M個查詢。接下來的M行，每一行都有一個查詢。一個查詢至少包含一個查詢條件，至多合併4個條件。若有多個條件，條件之間都以一個空白字元作分隔。查詢字串至多40個字元。請對字典執行查詢，共將符合規則的結果輸出。

P.S.

本題中查詢語法與字典中所有英文字母皆為小寫字母。基本查詢條件中，星號只可能如題目敘述所列出的三種情況，出現在頭或出現在尾，或同時出現在頭和尾。舉例來說：a*b不會出現在本題的測資中，在本題中以上查詢會被寫成a* *b兩個條件。

輸出說明：

對於每一個查詢，請先輸出一行訊息：

Query i: query_string, n item(s) is found.

i表示這是第幾個query，從1開始數。query_string則是輸入資料中的查詢字串，n則是滿足查詢條件的單字個數。接下來請輸出所有滿足查詢條件的單字，一行一個。請依單字在輸入資料中的順序輸出。結尾請輸出一個空行以分隔不同次的查詢。

範例輸入： help

9
confidence
federal
confederation
fidelity
infidelity
confident
confidential
diffident
infidel
4
con*
*fed*
im*
*fid* *ent

範例輸出：

Query 1: con*, 4 item(s) is found.
confidence
confederation
confident
confidential

Query 2: *fed*, 2 item(s) is found.
federal
confederation

Query 3: im*, 0 item(s) is found.

Query 4: *fid* *ent, 2 item(s) is found.
confident
diffident

提示：

出處：

2005 NPSC 高中組決賽

作法 : 模擬

/**********************************************************************************/
/* Problem: b046 "E. 智慧型單字查詢" from 2005 NPSC 高中組決賽       */
/* Language: C                                                                   */
/* Result: AC (6ms, 1184KB) on ZeroJudge                                         */
/* Author: morris1028 at 2011-08-22 19:09:43                                     */
/**********************************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct {
   char s[1000];
}STRING;
STRING S[1000], Ask[10];
main() {
   int C = 0, n, m, k, a, b, c, d, e;
   char cha;
   while(scanf("%d", &n) == 1) {
       for(a = 0; a < n; a++)
           scanf("%s", S[a].s);
       scanf("%d", &m);
       while(m--) {
           k = 0;
           while(scanf("%s%c", Ask[k].s, &cha) == 2 && cha != '\n')
               k++;
           int Ans[1000], find = 0, l1, l2, f1, f2;
           for(a = 0; a < n; a++) {
               for(b = 0; b <= k; b++) {
                   l1 = strlen(Ask[b].s), l2 = strlen(S[a].s), f1 = 0, f2 = 0;
                   if(Ask[b].s[0] == '*' && Ask[b].s[l1-1] == '*') {
                       for(c = 0; c < l2; c++) {
                           f1 = 0;
                           for(d = c, e = 1; d < l2 && e < l1-1; d++, e++)
                               if(Ask[b].s[e] != S[a].s[d])
                                   {f1 = 1;break;}
                           if(e == l1-1 && f1 == 0)   {f2 = 1;break;}
                       }
                   } else if(Ask[b].s[0] == '*') {
                       f1 = 0;
                       for(c = l2-1, d = l1-1; c >= 0 && d >= 1; c--, d--)
                           if(Ask[b].s[d] != S[a].s[c])
                               {f1 = 1;break;}
                       if(d == 0 && f1 == 0) {f2 = 1;}
                   } else {
                       f1 = 0;
                       for(c = 0, d = 0; c < l2 && d < l1-1; c++, d++)
                           if(Ask[b].s[d] != S[a].s[c])
                               {f1 = 1;break;}
                       if(d == l1-1 && f1 == 0) {f2 = 1;}
                   }
                   if(f2 == 0) break;
               }
               if(b == k+1)
                   Ans[find++] = a;
           }
           printf("Query %d:", ++C);
           for(a = 0; a <= k; a++)   printf(" %s", Ask[a].s);
           printf(", %d item(s) is found.\n", find);
           for(a = 0; a < find; a++)
               printf("%s\n", S[Ans[a]].s);
           puts("");
       }
   }
   return 0;
}

我要檢舉

#b046#E. 智慧型單字查詢

台長： Morris

您可能對以下文章有興趣

[ZJ][KM算法] d210. 老問題

[NPSC][方格法] b256. E. 大風吹

b094. H. 數字拼盤 (IDA* 版本)

[ZJ] a361. A. 賓果遊戲

人氣(2,066) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: NPSC |
此分類下一篇:b069. A. 千里傳情
此分類上一篇:b207. F. 世界盃

回應(0)