d249: 94北縣賽-1-心意相通的指數(Match)
Tags :
Accepted rate : 31人/59人 ( 53% ) [非即時]
評分方式:
Tolerant

最近更新 : 2009-05-03 17:05

Content


問題描述
      最近日本的高中學生之間流傳著一種測驗兩個好朋友是否心意相通的方法:兩
個人分別利用七種顏色的珠子串成項鍊,再看看兩個人製作出來的項鍊的相似程
度。若這七種顏色的珠子分別以R、O、Y、G、B、I 及P 表示,請你寫一個程式來
計算兩個人心意相通的指數。
舉個例子來說,小珠和小麗分別做了兩條項鍊:
小珠的項鍊: RROYBGRB
小麗的項鍊: BRRYYBGGGG
若將這兩條項錬看成兩個字串,則其最長的相似子字串為RRYBG,(在找相似子字
串時,只要考慮珠子顏色的排列順序即可,不需考慮兩個珠子中間是否有其他不同
的珠子,如果有只要跳過即可),但是由於項鍊串成圓形的,在比對時要考慮不同的
比對起點,來找出最長的相似子字串。例如將小珠的項鍊旋轉一下,
旋轉後小珠的項鍊: BRROYBGR
則二個字串的最長相似子字串就變成RRYBGB 了。因此,上述這兩條項鍊真正的最
長相同子字串應該是RRYBGB 才對。而這兩條項鍊間的相似程度則可以利用下式計
算得到


相似程度值=   最長相似子字串長度的二倍/兩條項鍊長度的總和


兩條項鍊長度的總和
最長相似子字串長度的二倍
同時這個值也就是兩個人心意相通的指數。

 為了答案設置的方便所以限制只有小珠的可以旋轉 

條件限制
1. 輸入的兩組字串皆由R、O、Y、G、B、I 及P 七種字母組成且字串長度皆小於250。
2. 如果兩組字串沒有相似的子字串,請輸出“no"。
3. 如果兩組字串有一個以上的最長相似子字串,只要輸組任意一個最長相似子字串即可。
Input
輸入資料為二行由R、O、Y、G、B、I 及P 組成的字串。
Output
請輸出最長的相似子字串以及相似程度值(到小數點第二位,第三位以後四捨五
入)。
Sample Input
BRRYYBGOY
YYBOBRG
Sample Output
YYBOBR
0.75
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <1K
Hint :
Tags:
出處:
94學年度北基區資訊學科能力競賽 [管理者:
nanj0178 (nanj)
]


ID User Problem Subject Hit Post Date
19836
jackyname1@gmai... (☆♬○♩程式家小崴●♪✧♩)
d249
41 2019-11-03 11:57
12980
sdf6ry6j (等於等於)
d249
優先權
300 2017-11-14 19:37