3.朋友 (104北二區 桃竹苗 )
問題描述
當我們到一個新環境時,常常會從和我們有相同個性、喜好或來自相同故鄉的人們開始結交,我們也會對同姓交或名字相近的人感到熟悉或有好感。 在這道題目中,我們將假設朋友關係是這樣建立的:
(1)若兩個人的名字相似,則兩個人會結為朋友。
(2)若兩個人有共同朋友,則兩個人會結為朋友。
如何定義兩個人的名字相似呢?令兩個人的名字為 S 和 T ,我們說若S(長度為m)和T(長度為n)的最長共同子字串(Longest common subsequene,LCS)長度不小於min(m,n)/2.0,則S和T相似。 {LCS的定義就省略}
根據上上述的朋友關係,我們可以將一群人分成一個或數個團體,每個團體中的任意兩個人都是朋友,而兩個不同團體中的人則都不是朋友。現在,請你寫一個程式,輸出最大團體(人數最多)的人數個數。
輸入測資檔第一行有一正整數T(1<=T<=3),代表有T組資料,每組第1行正整數N(1<=N<=50)行,接著N行,每行有一個人的名字,全數讚小寫英文字母組成,長度為L(1<=L<=50)。
每一組資料,輸出一行,最大團體的人數個數
3 5 abc adb xyzzzz zzzxop xompn 5 abc adb xyzzzz zzzxop xoapd 5 abc adb xyzzzz zzzxop xoape
3 5 3
測資有誤,感謝 liouzhou_101 指正
ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」
|