回分類題庫
d078: 5.解密
關鍵字: 105年台中區複賽

測資點 : 5 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 46 Times / 41 Users | Submit : 122 Times / 46 Users | Accepted rate : 89%
題目加入時間 : 2017-09-04 09:52

Content: 简体中文

對於英文句子,我們可以發現,若我們保留句中每一個單字頭尾的字母不動但將中間的字母任意打亂,我們還是可以很容易的識別出該英文句子中每個字的原始意義,例如 “tihs snetncee mkaes prfecet sesne”此例句中的每個單字大部分的人應該不難看出是 “this sentence makes perfect sense”;同樣的若我們將句子中的空格都移除把所有單字都串起來,也不難看出該句子的原始意義,例如 “thissentencemakesperfectsense”就是一個好的範例,然而若我們將一個句子依序做了以上兩種處裡(先打亂再移除空格),那要將原始句子中的單字都正確找出就不是一件容易的事,例如以下的字串就不容易還原成原來正確句子 “tihssnetnceemkaesprfecetsesne”

給定一個經過上述處理所得的字串以及一些字串中所用的單字所形成的字典,請寫一程式將字串解密成原來的句子。 

Input:

第一行為一個正整數 n (n≤100),代表接下來有 n 組測資。

每一組測資的開頭為一行任意打亂的英文句子(一個連續的小寫英文字母字串,其長度不大於 1000),下一行為一個正整數 k,代表該組測資的字典有 k (k≤100) 個單字。接下來的 k 行,每行會有一個單字(一個連續的小寫英文字母字串,其長度不大於 100)。 

Output:

每一組測資請輸出一行結果。

若根據字典內容,句子僅有一種解碼方式,則輸出解碼後的句子,單字間以一個空白字元分隔;若句子有多種解碼方式則輸出1;若句子無法解碼則輸出-1。 

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
tihssnetnceemkaesprfecetsesne
5
makes
perfect
sense
sentence
this
hitehre
2
there
hello
hitehre
3
hi
there
three

Sample Output :

this sentence makes perfect sense
-1
1

Hint :

Author :

105年台中區複賽 (管理員:sagit)

  Solve it!   Status Forum