d249. 94北縣賽-1-心意相通的指數(Match)
標籤 :
通過比率 : 31人/63人 ( 49% ) [非即時]
評分方式:
Tolerant

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

內容


問題描述
      最近日本的高中學生之間流傳著一種測驗兩個好朋友是否心意相通的方法:兩
個人分別利用七種顏色的珠子串成項鍊,再看看兩個人製作出來的項鍊的相似程
度。若這七種顏色的珠子分別以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. 如果兩組字串有一個以上的最長相似子字串,只要輸組任意一個最長相似子字串即可。
輸入說明
輸入資料為二行由R、O、Y、G、B、I 及P 組成的字串。
輸出說明
請輸出最長的相似子字串以及相似程度值(到小數點第二位,第三位以後四捨五
入)。
範例輸入 #1
BRRYYBGOY
YYBOBRG
範例輸出 #1
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
提示 :
標籤:
出處:
94學年度北基區資訊學科能力競賽 [管理者: nanj0178 (nanj) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
19836 jackyname1@g ... (☆♬○♩程式家小崴●♪✧♩) d249
687 2019-11-03 11:57
12980 sdf6ry6j (等於等於) d249
優先權
951 2017-11-14 19:37