b096. 黏著劑 - 旦旦解題農場

內容

題目敘述

給予兩字串 $A,B$ ，你可以進行以下操作一次(也可以不進行):

對 $A$ 提取連續子字串 $C$ ，對 $B$ 提取連續子字串 $D$ (假設 $B$ 為abc，則 $D$ 可為a，b，c，ab，bc，abc，但不可為ba,ac,cba...)，並假設 $C$ 有 $c$ 項， $D$ 有 $d$ 項

如果 $C$ 的第一項字元與 $D$ 的最後一項字元相同，則可組成新字串 $E$ 為 $D_1,D_2,...D_d,C_1,C_2,...,C_c$

如果 $C$ 的最後一項字元與 $D$ 的第一項字元相同，則可組成新字串 $E$ 為 $C_1,C_2,...,C_c,D_1,D_2,...D_d$

若不進行， $E$ 可為 $A$ 或 $B$

求出字串 $E$ 的最長長度

輸入說明

第一行輸入字串 $a,b$ 的長度 $A,B$

第二行輸入字串 $a$

第三行輸入字串 $b$

輸出說明

輸出最長字串長度

範例輸入

3 6
abc
decafg

範例輸出

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (9%): 1.0s , <1K
公開測資點#1 (9%): 1.0s , <1K
公開測資點#2 (9%): 1.0s , <1K
公開測資點#3 (9%): 1.0s , <1K
公開測資點#4 (9%): 1.0s , <1M
公開測資點#5 (9%): 1.0s , <1M
公開測資點#6 (8%): 1.0s , <1M
公開測資點#7 (8%): 1.0s , <1K
公開測資點#8 (3%): 1.0s , <10M
公開測資點#9 (3%): 1.0s , <10M
公開測資點#10 (3%): 1.0s , <10M
公開測資點#11 (3%): 1.0s , <10M
公開測資點#12 (3%): 1.0s , <10M
公開測資點#13 (3%): 1.0s , <10M
公開測資點#14 (2%): 1.0s , <10M
公開測資點#15 (2%): 1.0s , <10M
公開測資點#16 (2%): 1.0s , <10M
公開測資點#17 (2%): 1.0s , <10M
公開測資點#18 (2%): 1.0s , <10M
公開測資點#19 (2%): 1.0s , <10M

提示：

範例中 $C$ 為abc, $D$ 為cafg，可得到的最長字串為abccafg，長度為7

測資限制

$70\%$

$1 \leq A,B \leq 1000$

字串 $a,b$ 只包含小寫英文字母

$100\%$

$1 \leq A,B \leq 10^6$

字串 $a,b$ 只包含小寫英文字母

標籤:

12th初階班下學期期末考

出處:

[管理者：

Vandrin (357-10林明緯)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」