阿里巴巴能打開石門,是因為他知道「芝麻開門」的密語;烹飪高手能征服大家的味蕾,是因為他練就一身功夫,抓到美味的訣竅;演員能成功詮釋某個角色,必然是因為他對人生的悲歡離合有深刻的體會。對於人生的考驗,是否也有自己的「通關密語」,請以「通關密語」為題,寫下找出「密語」而得以「通關」的過程,以及其中的體會,文長不限。
參加103年學測的小玟看到了這樣的題目後,馬上「振筆疾書」在他的答案卷上寫下長度為$L_1\leq 5\times 10^ 4$的,屬於他的通關密語(真的得「疾書」才能在時間內寫完)。雖然是國文科的寫作,但是小玟非常堅持地把他的通關密語用介在a到j的小寫英文字母寫下來。
隔壁的小明一聽到從他隔壁傳來不間斷地筆接觸到桌面的聲音,咚咚咚咚地,因此而感到非常緊張。他實在沒有時間看引導,所以決定直接抄小玟的作文了。然而抄到一半的時候,小明發現他抄錯了!他寫下的$L_2\leq 5\times 10^ 4$個字元跟小玟的不太一樣,但他也沒時間重頭來過了。所以他決定找一個「最佳擬合」的平移方法,然後再繼續抄。所謂的「最佳擬合」,就是將小明的字串經過平移後和小玟的字串比對,同樣的字元數最多的那一種方法。
然而小明連找最佳擬合的時間也沒有了!為了小明的學測成績,請利用程式計算最佳擬合的方案。
每一組測資包含兩行,每行包含一個長度不超過$5\times 10^ 4$的字串。第一行是小玟的字串,第二行是小明的字串,雖然顛倒過來答案也不變所以這不太重要。
子任務(測資) | 額外限制 | 分數 |
1 (0~4) | $L_1, L_2\leq 10^ 4$ | 28 |
2 (5~9) | 只有a和b兩種字元 | 36 |
3 (0~14) | 無限制 | 36 |
請輸出一個正整數,代表最佳擬合的方案下,相同的字元有幾個。
ababa
..babab
這是一種最佳擬合的方法
Problem set / Description by Paupière
題目取自2015 TOI第一階段選訓第一次模擬考pB
No. | Testdata Range | Score |
---|---|---|
1 | 0~4 | 28 |
2 | 5~9 | 36 |
3 | 0~14 | 36 |