coolslogans

Cool Slogans

Bomboslav set up a branding agency and now helps companies to create new logos and advertising slogans. In term of this problems, slogan of the company should be a non-empty substring of its name. For example, if the company name is "hornsandhoofs", then substrings "sand" and "hor" could be its slogans, while strings "e" and "hornss" can not.

Sometimes the company performs rebranding and changes its slogan. Slogan A is considered to be cooler than slogan B if B appears in A as a substring at least twice (these occurrences are allowed to overlap). For example, slogan A = "abacaba" is cooler than slogan B = "ba", slogan A = "abcbcbe" is cooler than slogan B = "bcb", but slogan A = "aaaaaa" is not cooler than slogan B = "aba".

You are given the company name w and your task is to help Bomboslav determine the length of the longest sequence of slogans s1,s2,,sk, such that any slogan in the sequence is cooler than the previous one.

Limits

1n=|w|2×105.

Subtask # Score Constraints
1 5 n50
2 24 n4000
3 17 There exists an s1,s2,,sk with maximum k in which all s1,s2,,sk are prefixes of w.
4 54 No additional constraints

Input format

The input consists of a string of lowercase English letters on a single line, w.

Output format

Output a the single integer - the maximum possible length of the sequence of slogans of the company named w, such that any slogan in the sequence (except the first one) is cooler than the previous.

Samples

Sample Input 1 Sample Output 1
qaqaqzz 3

Explanation
s1= qaqaqzz
s2= qaq
s3= q

Sample Input 2 Sample Output 2
dabcabcabcabca 5

Explanation
s1= abcabcabcabca
s2= abcabcabca
s3= abcabca
s4= abca
s5= a

Sample Input 3 Sample Output 3
abracadabra 3

Explanation
s1= abracadabra
s2= abra
s3= a



Submitting .cpp to 'coolslogans'


You're not logged in! Click here to login

Time Limit: 2 Seconds
Memory Limit: 512MB
Your best score: 0
Source: LOJ #6288

Subtask Score
1 5
2 24
3 17
4 54