1076 . E.智慧型單字查詢
TopCoder
Tags
Description
小批為了增加自己的英文能力，找來了一本單字書打算好好的來背單字。可是單字書上的單字真的太多了，硬背的教果實在不太好。學校的英文老師這時教了用字首字根拆解來認識英文單字的方法。
字首包括 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 合併的情形。)
Input Format
輸入檔前半部包含一部字典。第一行有一個整數 $N (1 ≤ N ≤ 1000)$，代表一共有 $N$ 個單字。接下來 $N$ 行，每一行有一個小寫英文單字。輸入檔的後半部有數個查詢。後半部第一行有一個整數 $M (1 ≤ M ≤ 1000)$，代表一共有 $M$ 個查詢。接下來的 $M$ 行，每一行都有一個查詢。一個查詢至少包含一個查詢條件，至多合併 $4$ 個條件。若有多個條件，條件之間都以一個空白字元作分隔。查詢字串至多 $40$ 個字元。請對字典執行查詢，共將符合規則的結果輸出。
P.S.
本題中查詢語法與字典中所有英文字母皆為小寫字母。基本查詢條件中，星號只可能如題目敘述所列出的三種情況，出現在頭 或出現在尾，或同時出現在頭和尾。舉例來說：a*b 不會出現在本題的測資中，在本題中以上查詢會被寫成 a* *b 兩個條件。
Output Format
對於每一個查詢，請先輸出一行訊息：
Query i: query_string, n item(s) is found.
i 表示這是第幾個 query，從 $1$ 開始數。query_string 則是輸入資料中的查詢字串，n 則是滿足查詢條件的單字個數。接下來請輸出所有滿足查詢條件的單字，一行一個。請依單字在輸入資料中的順序輸出。結尾請輸出一個空行以分隔不同次的查詢。
Sample Input 1
confidence
federal
confederation
fidelity
infidelity
confident
confidential
diffident
infidel
4
con*
*fed*
im*
*fid* *ent
Sample Output 1
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
Hints
Problem Source
原TIOJ1076 / NPSC2005決賽(prob E)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 100 |