G - Exam Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200

問題文

京都大学の一般入試を翌日に控えているあなたは, 試験に出題されそうな文字列集合 S を覚えることにした. しかし,S を覚えるのは面倒なので,代わりに語呂合わせとして文字列 T を覚えることにして, ST について以下の条件を満たすことを確認した.

  • 任意の S の要素は T連続する部分文字列(1) である.
  • 任意の S の要素の組 x, y (x \neq y) について, xy の部分列(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
このときは, abcabc と復元した場合が最大となる例の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

3
In this case, abca 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

Source Name

KUPC2016