1515 . Problem E. 似曾相識

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

77.2% (44/57)

Submission's AC Ratio

30.9% (94/304)

Tags

Description

任添糖遊戲公司最近推出了一款老少咸宜的遊戲「似曾相似」

在遊戲的一開始你會拿到兩個一模一樣的字串S

而你的目標是將這兩個字串(不可顛倒不然盒子會咬人)放進

　我是字串長度-1|
|_______________

如上形狀的神奇盒子裡，而盒子的長度正好是S的長度-1

完成後得到的分數 = 盒子內最長一串上下相同的字的長度

例：
S = "XDXDXDrz"

則我們可以這樣放

其中XDXD為上下相同且最長的字串，故得分為4分

Input Format

第一行包含一個整數 N(N<=200000)，代表字串 S 的長度，

第二行則是一個長度為 N 的字串 S。

Output Format

一個整數 P 代表最大得分。

Sample Input 1

8
XDXDXDrz

Sample Output 1

4

Hints

※2008.02.28 補上範例圖片。- skyly

Problem Source

原TIOJ1515 / Problem Setter: shik

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1500 65536 262144 1
1 1500 65536 262144 2
2 1500 65536 262144 3
3 1500 65536 262144 4
4 1500 65536 262144 5
5 1500 65536 262144 6
6 1500 65536 262144 7
7 1500 65536 262144 8
8 1500 65536 262144 9
9 1500 65536 262144 10
Submit
Back to Top