b046. E. 智慧型單字查詢
內容 ：
小批為了增加自己的英文能力，找來了一本單字書打算好好的來背單字。可是單字書上的單字真的太多了，硬背的教果實在不太好。學校的英文老師這時教了用字首字根拆解來認識英文單字的方法。
字首包括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則是滿足查詢條件的單字個數。接下來請輸出所有滿足查詢條件的單字，一行一個。請依單字在輸入資料中的順序輸出。結尾請輸出一個空行以分隔不同次的查詢。
範例輸入
：
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
提示
：
出處
：
作法 : 模擬
/**********************************************************************************/
/* 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;
}
上一篇：b207. F. 世界盃
下一篇：b069. A. 千里傳情