TopCoder

WeaK
weak.infor.org 雖然這裡好像沒什麼東西。

User's AC Ratio

50.0% (3/6)

Submission's AC Ratio

11.8% (4/34)

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

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

Sample Output

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

Hints

Problem Source

原TIOJ1076 / NPSC2005決賽(prob E)

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 30000 65536 65536