/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 200 点
問題文
京都大学の一般入試を翌日に控えているあなたは， 試験に出題されそうな文字列集合 S を覚えることにした． しかし，S を覚えるのは面倒なので，代わりに語呂合わせとして文字列 T を覚えることにして， S と T について以下の条件を満たすことを確認した．
- 任意の S の要素は T の連続する部分文字列(1) である．
- 任意の S の要素の組 x, y (x \neq y) について， x は y の部分列(2) でない．
ただし，(1) は「連続する部分列」であり，(2) は「部分列」であることに注意されたい．
翌日，試験が開始して答案用紙を開くと，どうやら S さえ覚えていれば満点を取れそうだということがわかった． しかし，あなたは文字列 T から S への復元のしかたを忘れてしまった． 文字列 T の他に上の条件を満たすことだけは覚えているので， まずは S の要素数としてありえる最大値を求めることにした．
制約
- 1 \leq |T| \leq 10^5
- 含まれる文字の種類は半角アルファベット小文字のみ
部分点
- 1 \leq |T| \leq 50 を満たす全てのテストケースに正解した場合，部分点として 30 点が与えられる．
- 1 \leq |T| \leq 10^3 を満たす全てのテストケースに正解した場合，部分点としてさらに 30 点が与えられる．
入力
入力は以下の形式で標準入力から与えられる．
T
入力は文字列 T の 1 行のみからなる．
出力
S の要素数の最大値を出力せよ．
入力例1
abcabc
出力例1
3このときは，
ab，ca，bc と復元した場合が最大となる例の1つである
入力例2
abracadabra
出力例2
7
入力例3
abcbabbcabbc
出力例3
8
入力例4
bbcacbcbcabbabacccbbcacbaaababbacabaaccbccabcaabba
出力例4
44
Score : 200 points
Problem Statement
You are going to take the entrance examination of Kyoto University tomorrow and have decided to memorize a set of strings S that is expected to appear in the examination. Since it is really tough to memorize S as it is, you have decided to memorize a single string T that efficiently contains all the strings in S.
You have already confirmed the following conditions for S and T are satisfied.- Every string in S is a consecutive subsequence(1) in T .
- For every pair of strings x, y (x \neq y) in S , x is not a subsequence(2) of y.
Note that (1) is ''consecutive subsequence'', while (2) is ''subsequence''.
The next day, you opened the problem booklet at the examination and found that you can get a full score only if you remember S. However, You have forgot how to reconstruct S from T . Since all you remember is that T satisfies the above conditions, first you have decided to find the maximum possible number of elements in S .
Constraints
- 1 \leq |T| \leq 10^5
- T consists of only lowercase letters.
Partial points
- 30 points will be awarded for passing the test set satisfying the condition: 1 \leq |T| \leq 50 .
- Another 30 points will be awarded for passing the test set satisfying the condition: 1 \leq |T| \leq 10^3.
Input
The input is given from Standard Input in the following format:
T
The input only consists of T on one line.
Output
Print the maximum number of elements inS .
Sample Input 1
abcabc
Sample Output 1
3In this case,
ab，ca and bc are an example of the optimum answers.
Sample Input 2
abracadabra
Sample Output 2
7
Sample Input 3
abcbabbcabbc
Sample Output 3
8
Sample Input 4
bbcacbcbcabbabacccbbcacbaaababbacabaaccbccabcaabba
Sample Output 4
44