15 . 最長共同回文子序列

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

餘切
$\huge\text{owoovo is 8}$

User's AC Ratio

94.9% (37/39)

Submission's AC Ratio

68.8% (106/154)

Tags

ioicamp ioicamp-2024

Description

給定兩個長度分別為 $N, M$ 的字串 $a, b$，請輸出滿足以下條件的字串 $c$ 的長度：

  • $c$ 為 $a$ 的子序列
  • $c$ 為 $b$ 的子序列
  • $c$ 為回文字串
  • $c$ 為所有滿足以上三條的字串中最長的

定義 $|s|$ 為 $s$ 的長度。

字串 $t$ 為字串 $s$ 的子序列若存在一個序列 $a_1, a_2, \ldots, a_{|t|}$ 滿足 $1 \leq a_1 < a_2 < \ldots < a_{|t|} \leq |s|$ 且 $t_i = s_{a_i} \forall 1 \leq i \leq |t|$。

字串 $s$ 為回文字串若 $s_i = s_{|s| + 1 - i} \forall 1 \leq i \leq |s|$。

Input Format

輸入第一行有兩個正整數 $N, M$，代表字串 $a$ 與字串 $b$ 的長度。
輸入第二行有一個長度為 $N$ 且僅由小寫英文字母組成的字串 $a$。
輸入第三行有一個長度為 $M$ 且僅由小寫英文字母組成的字串 $b$。

  • $1 \leq N, M \leq 80$
  • $|a| = N, |b| = M$
  • $a, b$ 的每個字元皆為小寫英文字母

Output Format

請輸出一行，上面有一個整數代表字串 $c$ 的長度

Sample Input 1

8 8
acbcabaa
aabbccba

Sample Output 1

5

Sample Input 2

14 8
ioicampisgreat
wiwihorz

Sample Output 2

2

Sample Input 3

7 7
rotator
rotator

Sample Output 3

7

Hints

在第一筆範例測資中，$c = \texttt{abcba}$

在第二筆範例測資中，$c = \texttt{ii}$

在第三筆範例測資中，$c = \texttt{rotator}$

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 3~28 $1 \leq N, M \leq 15$ 10
3 3~46 $1 \leq N, M \leq 35$ 19
4 47~65 $N = M, a_i = b_i \forall 1 \leq i \leq N$ 26
5 3~83 無其他限制 45

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 1048576 65536 1
1 3000 1048576 65536 1
2 3000 1048576 65536 1
3 3000 1048576 65536 2 3 5
4 3000 1048576 65536 2 3 5
5 3000 1048576 65536 2 3 5
6 3000 1048576 65536 2 3 5
7 3000 1048576 65536 2 3 5
8 3000 1048576 65536 2 3 5
9 3000 1048576 65536 2 3 5
10 3000 1048576 65536 2 3 5
11 3000 1048576 65536 2 3 5
12 3000 1048576 65536 2 3 5
13 3000 1048576 65536 2 3 5
14 3000 1048576 65536 2 3 5
15 3000 1048576 65536 2 3 5
16 3000 1048576 65536 2 3 5
17 3000 1048576 65536 2 3 5
18 3000 1048576 65536 2 3 5
19 3000 1048576 65536 2 3 5
20 3000 1048576 65536 2 3 5
21 3000 1048576 65536 2 3 5
22 3000 1048576 65536 2 3 5
23 3000 1048576 65536 2 3 5
24 3000 1048576 65536 2 3 5
25 3000 1048576 65536 2 3 5
26 3000 1048576 65536 2 3 5
27 3000 1048576 65536 2 3 5
28 3000 1048576 65536 2 3 5
29 3000 1048576 65536 3 5
30 3000 1048576 65536 3 5
31 3000 1048576 65536 3 5
32 3000 1048576 65536 3 5
33 3000 1048576 65536 3 5
34 3000 1048576 65536 3 5
35 3000 1048576 65536 3 5
36 3000 1048576 65536 3 5
37 3000 1048576 65536 3 5
38 3000 1048576 65536 3 5
39 3000 1048576 65536 3 5
40 3000 1048576 65536 3 5
41 3000 1048576 65536 3 5
42 3000 1048576 65536 3 5
43 3000 1048576 65536 3 5
44 3000 1048576 65536 3 5
45 3000 1048576 65536 3 5
46 3000 1048576 65536 3 5
47 3000 1048576 65536 4 5
48 3000 1048576 65536 4 5
49 3000 1048576 65536 4 5
50 3000 1048576 65536 4 5
51 3000 1048576 65536 4 5
52 3000 1048576 65536 4 5
53 3000 1048576 65536 4 5
54 3000 1048576 65536 4 5
55 3000 1048576 65536 4 5
56 3000 1048576 65536 4 5
57 3000 1048576 65536 4 5
58 3000 1048576 65536 4 5
59 3000 1048576 65536 4 5
60 3000 1048576 65536 4 5
61 3000 1048576 65536 4 5
62 3000 1048576 65536 4 5
63 3000 1048576 65536 4 5
64 3000 1048576 65536 4 5
65 3000 1048576 65536 4 5
66 3000 1048576 65536 5
67 3000 1048576 65536 5
68 3000 1048576 65536 5
69 3000 1048576 65536 5
70 3000 1048576 65536 5
71 3000 1048576 65536 5
72 3000 1048576 65536 5
73 3000 1048576 65536 5
74 3000 1048576 65536 5
75 3000 1048576 65536 5
76 3000 1048576 65536 5
77 3000 1048576 65536 5
78 3000 1048576 65536 5
79 3000 1048576 65536 5
80 3000 1048576 65536 5
81 3000 1048576 65536 5
82 3000 1048576 65536 5
83 3000 1048576 65536 5
Submit
Back to Top