TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

Description

撰寫歌詞一直以來都是一個辛苦的工作,身為 Aqours 中負責寫歌詞的高海千歌,每次都要絞盡腦汁花費大量心思才能寫出一個符合期待的歌詞,尤其是在寫了這麼多歌曲後,想要能有突破性的創作實在是件困難的事。

最近的她為了寫歌,每天都吃不下飯,讓人非常心疼。更糟糕的是明天就是約定的交稿日了,千歌還是寫不出一個能夠溫暖人心卻又不失 Aqours 風格的歌詞,於是她向你求助,希望你能幫助她完成歌曲。

而你除了認識千歌外,也剛好與聖翔音樂學園的神樂光非常要好,因為平常神樂光也會向你討論歌詞的內容,所以你其實也有小光所寫的許多歌詞,於是你決定融合兩者的風格,把千歌給你的草稿中的一小部分歌詞換成小光寫的歌詞。

然而為了不要讓人一眼識破你其實是抄襲他人的歌曲,你在把小光的歌詞放入千歌的歌曲時,會希望小光的歌詞與千歌被換掉的那一部分歌詞的「最長共同前綴長度加上最長共同後綴長度」越長越好,這樣的話相信粉絲們如果不認真檢查應該都檢查不出來。此外,為了搭配樂曲本身,你也希望被換掉的歌詞的字數要與小光的歌詞字數一樣長。

現在你手上有著千歌給你的草稿了,而你也精心挑選的一小段小光的歌詞了,你可以把千歌歌詞中的任一一段換成小光的歌詞,現在貴想知道千歌被換掉的歌詞與小光的歌詞的「最長共同前綴長度加上最長共同後綴長度」最長可以是多長。特別的,如果兩段歌詞完全一樣,此時這個長度被定義為原本小光的歌詞的長度。

請你告訴貴這個問題的答案吧!(你肯定不會讓貴失望的吧?)

Input Format

第一行輸入兩個整數 $n,m$ 分別代表千歌的草稿的長度和小光的歌詞的長度。

第二行輸入一個字串,代表千歌的草稿。

第三行輸入一個字串,代表小光的歌詞。

  • $1 \leq m \leq n \leq 10^ 6$
  • 保證輸入的字串都由小寫英文字母構成。

Output Format

輸出一個整數,代表千歌被換掉的歌詞與小光的歌詞的「最長共同前綴長度加上最長共同後綴長度」最長可以是多長。

Sample Input 1

5 3
aacbb
adb

Sample Output 1

2

Sample Input 2

5 3
abbba
bbb

Sample Output 2

3

Hints

Problem Source

IOICamp 2021 Day5 pJ

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~18 無額外限制 100

Testdata and Limits

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