回分類題庫
z054: E. 數位文獻修復
關鍵字: 2013 NPSC 國中組初試

測資點 : 1 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 35 Times / 35 Users | Submit : 49 Times / 38 Users | Accepted rate : 92%
題目加入時間 : 2018-11-14 16:22

Content: 简体中文

對於較有歷史、古老的典籍,要妥善地保存是相當困難的。尤其是古代書寫的紙張,不僅本身可能會破損、風化,書寫於其上的文字也可能再經過數千年的時間後淡化。在這種情形之下,其 實是很難供眾人查閱內容的,畢竟光是要保存都需花費很大的功夫了。如果任意翻閱,可能會破壞到典籍本身。

故現代掀起一陣數位文獻典藏的潮流,對於一些以前的文物、文獻,我們可以用將其數位化的方式保存。對於一些古人的手抄文本等書籍,如果我們有辦法將內容輸入至電腦、資料庫中保存的話,就不用擔心有朝一日會再也讀不出內文了。

然而,有些典籍文本經過歲月的摧殘,上頭有些字跡早已模糊不清,或者是有所破損。對於這類的文字,有許多是我們很難做修補的。

有一天,曉涵在圖書館查閱相關資料時發現,有些內容有所缺漏,而數位文本竟然有超過一個來源。重要的是,從不同來源數位文本,有所殘缺的地方還不一定相同!聰明的曉涵於是便想到,「如果兩份理應相同的文本能夠互相填補缺失,那不是太棒了?」於是,曉涵找出了所有有兩 種以上來源的相同文本,並嘗試想要修補它們。

然而,有的文本不管在哪個來源的電子化內容中,有些位置總是都缺失了,那我們就沒有辦法將其內容經由交互比對來完全復原。

為了簡化題目,我們將每份文獻資料當作一個字串,並且假設給定的文獻資料都只有兩個不同的來源。請你寫一個程式幫幫曉涵,判斷每一組給定的文獻有沒有辦法藉由相互比較完全復原。

Input:

輸入的第一行有一個正整數 T(T 50),代表測試資料的組數。

每一筆測試資料有兩行,分別對應到兩個來源的文獻內容。每一篇文獻都是以一個長度不超過 1024 的字串表示。其中,對於破損的字元,在輸入中將以問號 "?”(不含雙引號) 字元表示。

所有輸入的文獻內容保證除了表示破損的 "?” 之外,只會出現大寫英文字母及小寫英文字母。 並且,輸入保證兩個給定的字串皆至少有一個 "?” 字元。兩個字串除了 "?” 以外的內容將完全相同。

Output:

對於每一筆測試資料,請輸出一行。

如果曉涵有辦法成功完全修復整份文獻資料的話,請輸出”Yes:”(不含雙引號),之後緊接著是 修復完全的文獻內容;反之,沒有辦法的話,請輸出一行”No” (注意:請不要在任何地方自行加上空白或其他字元。)

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
5 
De?rMyFrien? 
DearM??riend 
?????????????sAndAlgorithms 
DataStructuresAnd?????????s 
?ffect 
?ffect 
ant?diluvian 
ant?diluv?an 
NPS? 
N?SC

Sample Output :

Yes:DearMyFriend 
Yes:DataStructuresAndAlgorithms 
No 
No 
Yes:NPSC

Hint :

Author :

2013 NPSC 國中組初試 (管理員:Chang)

  Solve it!   Status Forum