1505 . 鳩尾榫

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Enzo

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

60.0% (3/5)

Tags

ytp ytp2026 ytp-senior

Description

費伯有兩條紙帶，分別記為 $A$ 和 $B$。每條紙帶上都印著一排英文字母。我們用 $|A|$ 和 $|B|$ 分別表示紙帶 $A$ 和 $B$ 上字母的數量。

他想把兩條紙帶接成一個圈。接法是先把 $B$ 的尾端疊到 $A$ 的開頭，再把 $A$ 的尾端疊到 $B$ 的開頭。疊在一起的地方，兩條紙帶上的字母必須完全相同，接起來才不會突兀。

第一段重疊是 $B$ 結尾的一段配上 $A$ 開頭的一段。第二段重疊則是 $A$ 結尾的一段配上 $B$ 開頭的一段。兩段重疊都可以是空的，但為了接成圈，任何一段重疊都不能用掉某一條紙帶上的全部字母。一條紙帶上的每個字母只能用來重疊一次，因此同一條紙帶上的兩段重疊不能共用任何字母（可以緊鄰）。

費伯希望重疊的字母越多越好。請問兩段重疊的總長度最多是多少？

Input Format

第一行有一個字串 $A$，代表第一條紙帶上由左到右的符號。

第二行有一個字串 $B$，代表第二條紙帶上由左到右的符號。

  • $1 \leq |A|, |B| \leq 10^ 6$
  • $A$ 和 $B$ 只由小寫英文字母組成。

Output Format

輸出一個整數，代表兩段重疊總共最多能疊起幾個符號。

Sample Input 1

terminal
alter

Sample Output 1

5

Sample Input 2

zzzz
zz

Sample Output 2

2

Hints

範測 1 解釋：

$A$ 開頭與 $B$ 結尾的 ter 可以疊在一起，$B$ 開頭與 $A$ 結尾的 al 可以疊在一起，總長度為 $5$。

範測 2 解釋：

$A$ 開頭與 $B$ 結尾的 z 可以疊在一起，$B$ 開頭與 $A$ 結尾的 z 可以疊在一起，總長度為 $2$。

Problem Source

2026 YTP 高中組決賽 p4

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測試資料 0
2 2~9 $A = B$ 3
3 0~1, 10~19 $|A|, |B| \leq 5000$ 3
4 0~28 無額外限制 9

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 1048576 65536 1 3 4
1 1000 1048576 65536 1 3 4
2 1000 1048576 65536 2 4
3 1000 1048576 65536 2 4
4 1000 1048576 65536 2 4
5 1000 1048576 65536 2 4
6 1000 1048576 65536 2 4
7 1000 1048576 65536 2 4
8 1000 1048576 65536 2 4
9 1000 1048576 65536 2 4
10 1000 1048576 65536 3 4
11 1000 1048576 65536 3 4
12 1000 1048576 65536 3 4
13 1000 1048576 65536 3 4
14 1000 1048576 65536 3 4
15 1000 1048576 65536 3 4
16 1000 1048576 65536 3 4
17 1000 1048576 65536 3 4
18 1000 1048576 65536 3 4
19 1000 1048576 65536 3 4
20 1000 1048576 65536 4
21 1000 1048576 65536 4
22 1000 1048576 65536 4
23 1000 1048576 65536 4
24 1000 1048576 65536 4
25 1000 1048576 65536 4
26 1000 1048576 65536 4
27 1000 1048576 65536 4
28 1000 1048576 65536 4
Submit
Back to Top