String Journey
Contest: Codeforces Round 516 (Div. 1, by Moscow Team Olympiad)
Difficulty rating: 3300
Tags: data structures, dp, string suffix structures

We call a sequence of strings t1, ..., tk a journey of length k, if for each i > 1 ti is a substring of ti - 1 and length of ti is strictly less than length of ti - 1. For example, {ab, b} is a journey, but {ab, c} and {a, a} are not.

Define a journey on string s as journey t1, ..., tk, such that all its parts can be nested inside s in such a way that there exists a sequence of strings u1, ..., uk + 1 (each of these strings can be empty) and s = u1 t1 u2 t2... uk tk uk + 1. As an example, {ab, b} is a journey on string abb, but not on bab because the journey strings ti should appear from the left to the right.

The length of a journey on a string is the number of strings in it. Determine the maximum possible length of a journey on the given string s.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 500 000) — the length of string s.

The second line contains the string s itself, consisting of n lowercase Latin letters.

Output format:
Print one number — the maximum possible length of string journey on s.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Note:
In the first sample, the string journey of maximum length is {abcd, bc, c}.

In the second sample, one of the suitable journeys is {bb, b}.

Example input:
7
abcdbcc

Example output:
3

Example input:
4
bbcb

Example output:
2

Editorial:
This problem required quite a lot of nice observations!
Observation 1. We can only consider journeys in which neighboring strings differ exactly by removing one symbol.
All other journeys can be modified a bit to match the criterion above.
Observation 2. If it is possible to start a journey at the symbol i with lengths of strings k, k - 1, ..., 1, it is always possible to start a journey at the same symbol i with lengths t, t - 1, ..., 1, given that t ≤ k.
This suggests doing dynamic programming: dp[i] is the maximum possible k such that there is a journey starting at position i of k strings with lengths k, ..., 1.
Due to observation 1 we only care about maximum – if we know maximum, we also known that all lesser values are also OK.
So let's calculate this dynamic programming from right to left.
How to check whether dp[i] ≥ k (given that tool, we can just use binary search for example)?
There must be such j, that j ≥ i + k, dp[j] ≥ k - 1 and string sj, ..., sj + k - 2 must be a substring of string sisi + 1... si + k - 1 (basically just two cases "left substring" or "right substring").
This almost gives us a solution, but we need few more observations to have $$O(n \log n)$$, and not $${ \mathcal { O } } ( n \log ^ { c } n )$$.
Observation 3. If dp[i] = k, then dp[i + 1] ≥ k - 1.
We can use this to kick binary search from the solution — when you calculate dp[i] you can start trying with dp[i + 1] + 1, descending until the success.
Since there are exactly n grows, there will be at most n descendings and the total number of checks is linear.
?Observation? 4. We need to check whether such j exists in a fast way.
Recall there are few conditions for us to follow, dp[j] ≥ const, j ≥ const and some string equality.
If you carefully look at the restriction j ≥ const you can see, that when we move our dp calculation i → i - 1 or make dp[i] -= 1 this lower bound on j also moves only left, like in two pointers. So each moment some indexes j are "available" and some are not, and the border moves only left.
Finally, time for some structures. Build Suffix Array and build segment tree over it. Let's store in the leaf of the segment tree dp[j] if it's already available or  - 1 otherwise.
Let's check whether dp[i] = k is good. We want for string starting at j be either si, si + 1, ..., si + k - 2, or si + 1, si + 2, ..., si + k - 1. Consider these cases independently (however the procedure is pretty much same).
All such strings form a segment of Suffix Array, we can for example use LCP + binary search over sparse tables to find corresponding bounds.
Then we just need to query this segment and check if the maximum on it is at least k - 1.
The solution is $$O(n \log n)$$