15 . 最長共同回文子序列

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

餘切
owoovo is 8

User's AC Ratio

92.7% (38/41)

Submission's AC Ratio

66.5% (107/161)

Tags

ioicamp ioicamp-2024

Description

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

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

定義 |s| 為 s 的長度。

字串 t 為字串 s 的子序列若存在一個序列 a1,a2,…,a|t| 滿足 1≤a1<a2<…<a|t|≤|s| 且 ti=sai∀1≤i≤|t|。

字串 s 為回文字串若 si=s|s|+1−i∀1≤i≤|s|。

Input Format

輸入第一行有兩個正整數 N,M，代表字串 a 與字串 b 的長度。

輸入第二行有一個長度為 N 且僅由小寫英文字母組成的字串 a。

輸入第三行有一個長度為 M 且僅由小寫英文字母組成的字串 b。

  • 1≤N,M≤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=abcba

在第二筆範例測資中，c=ii

在第三筆範例測資中，c=rotator

Problem Source

IOICamp 2024 PreExam pE

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 3~28 1≤N,M≤15 10
3 3~46 1≤N,M≤35 19
4 47~65 N=M,ai=bi∀1≤i≤N 26
5 0~83 無額外限制 45

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 1048576 65536 1 5
1 3000 1048576 65536 1 5
2 3000 1048576 65536 1 5
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