TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

78.6% (11/14)

Submission's AC Ratio

27.4% (26/95)

Description

阿里巴巴能打開石門,是因為他知道「芝麻開門」的密語;烹飪高手能征服大家的味蕾,是因為他練就一身功夫,抓到美味的訣竅;演員能成功詮釋某個角色,必然是因為他對人生的悲歡離合有深刻的體會。對於人生的考驗,是否也有自己的「通關密語」,請以「通關密語」為題,寫下找出「密語」而得以「通關」的過程,以及其中的體會,文長不限。

參加103年學測的小玟看到了這樣的題目後,馬上「振筆疾書」在他的答案卷上寫下長度為$L_1\leq 5\times 10^ 4$的,屬於他的通關密語(真的得「疾書」才能在時間內寫完)。雖然是國文科的寫作,但是小玟非常堅持地把他的通關密語用介在a到j的小寫英文字母寫下來。

隔壁的小明一聽到從他隔壁傳來不間斷地筆接觸到桌面的聲音,咚咚咚咚地,因此而感到非常緊張。他實在沒有時間看引導,所以決定直接抄小玟的作文了。然而抄到一半的時候,小明發現他抄錯了!他寫下的$L_2\leq 5\times 10^ 4$個字元跟小玟的不太一樣,但他也沒時間重頭來過了。所以他決定找一個「最佳擬合」的平移方法,然後再繼續抄。所謂的「最佳擬合」,就是將小明的字串經過平移後和小玟的字串比對,同樣的字元數最多的那一種方法。

然而小明連找最佳擬合的時間也沒有了!為了小明的學測成績,請利用程式計算最佳擬合的方案。

Input Format

每一組測資包含兩行,每行包含一個長度不超過$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

Output Format

請輸出一個正整數,代表最佳擬合的方案下,相同的字元有幾個。

Sample Input

ababa
babab

Sample Output

4

Hints

ababa
..babab
這是一種最佳擬合的方法

Problem Source

Problem set / Description by Paupière
題目取自2015 TOI第一階段選訓第一次模擬考pB

Subtasks

For Testdata: 0 ~ 4, Score: 28
For Testdata: 5 ~ 9, Score: 36
For Testdata: 0 ~ 14, Score: 36
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 3000 65536 65536
6 3000 65536 65536
7 3000 65536 65536
8 3000 65536 65536
9 3000 65536 65536
10 3000 65536 65536
11 3000 65536 65536
12 3000 65536 65536
13 3000 65536 65536
14 3000 65536 65536