TopCoder

Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

77.5% (138/178)

Submission's AC Ratio

33.0% (425/1287)

Tags

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 1

ababa
babab

Sample Output 1

4

Hints

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

Problem Source

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

Subtasks

No. Testdata Range Score
1 0~4 28
2 5~9 36
3 0~14 36

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1 3
1 1000 65536 262144 1 3
2 1000 65536 262144 1 3
3 1000 65536 262144 1 3
4 1000 65536 262144 1 3
5 3000 65536 262144 2 3
6 3000 65536 262144 2 3
7 3000 65536 262144 2 3
8 3000 65536 262144 2 3
9 3000 65536 262144 2 3
10 3000 65536 262144 3
11 3000 65536 262144 3
12 3000 65536 262144 3
13 3000 65536 262144 3
14 3000 65536 262144 3