TopCoder

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

User's AC Ratio

82.4% (14/17)

Submission's AC Ratio

34.7% (26/75)

Tags

Description

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

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

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


 我是字串長度-1|
|_______________

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

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

例:
S = "XDXDXDrz"

則我們可以這樣放

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

Input Format

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

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

Output Format

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

Sample Input

8
XDXDXDrz

Sample Output

4

Hints

※2008.02.28 補上範例圖片。- skyly

Problem Source

原TIOJ1515 / Problem Setter: shik

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1500 65536 262144
1 1500 65536 262144
2 1500 65536 262144
3 1500 65536 262144
4 1500 65536 262144
5 1500 65536 262144
6 1500 65536 262144
7 1500 65536 262144
8 1500 65536 262144
9 1500 65536 262144