TWICE - Twice
Given a string S, find the longest substring that appears at least twice in S (occurrences may overlap).
Input
The first line contains an integer L (1 ≤ L ≤ 200000), the length of S.
The second line contains the string S, consisting of exactly L lowercase letters ('a'-'z').
Output
Output the length of the longest substring that appears at least twice in S. If there is no such substring, output 0.
Example
Input:
11
sabcabcfabc
Output:
3
Input:
18
trutrutiktiktappop
Output:
4
hide comments
Ajey Golsangi:
2012-09-05 17:32:24
Nice problem. |
|
Buda IM (retired):
2012-02-25 22:59:20
Suffix array is not needed to solve this problem |
|
Nikhil Garg:
2010-12-27 17:14:08
Too bad - I don't know O(N) construction of suffix tree yet :( |
|
Lovro Puzar:
2009-08-24 14:52:50
> is substring of length 1 is also considered??
|
Added by: | Lovro Puzar |
Date: | 2009-08-21 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Own problem |