TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

73.7% (14/19)

Submission's AC Ratio

26.6% (17/64)

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

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

Sample Output 1

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

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1