COCI '06 Contest 5 #6 Dvaput

Points: 15 (partial)

Time limit: 0.6s

Java 2.0s

Memory limit: 32M

Problem type

Ivana won the bet (Zvonko hadn't foreseen this and suspects that it is due to outside interference) and now Zvonko is waiting for her at the movies. While he is waiting, he is observing messages on a screen above him.

As Ivana is running late, Zvonko has been looking at the screen for a while and noticed that some messages appeared on the screen more than once. Naturally, he's been writing down all messages on a piece of paper. He wants to know the length of the longest string that appeared at least twice (appears in two different positions on the paper).

Input Specification

The first line of input contains an integer $L$ ~L~ $(1 \le L \le 200\,000)$ ~(1 \le L \le 200\,000)~, the length of the string Zvonko wrote down.

The second line contains a string of $L$ ~L~ lowercase letters of the English alphabet.

Output Specification

Output the length of the longest string that appears twice on a single line. If there is no such string, output zero.

Sample Input 1

11
sabcabcfabc

Sample Output 1

Sample Input 2

18
trutrutiktiktappop

Sample Output 2

Sample Input 3

6
abcdef

Sample Output 3

Comments

4

noYou commented on May 27, 2020, 6:36 p.m.

Can the time limit be raised a bit so this is solveable in java? There are currently no submissions that make it to subtask 10.

9

septence123 commented on Aug. 13, 2017, 1:04 a.m.

Can they overlap?

6

Kirito commented on Aug. 13, 2017, 4:18 a.m.

Yes.

1

kobortor commented on Jan. 26, 2017, 2:41 a.m.

The game developers didn't intend for you to mod your games, and neither did this problem.