#include #define INF 2000000000 void set_segt (int *t, int idx, int val, int size) { idx = idx+size-1; t[idx] = val; while (idx > 0) { idx = (idx-1)/2; t[idx] = t[2*idx+1]; if (t[2*idx+2] > t[2*idx+1]) { t[idx] = t[2*idx+2]; } } return; } int get_segt (int *t, int idx, int size) { return t[idx+size-1]; } int max_segt_rec (int *t, int a, int b, int k, int l, int r) { int ans = 0; int tmp = 0; if (r <= a || b <= l) { return -INF; } if (a <= l && r <= b) { return t[k]; } ans = max_segt_rec(t, a, b, 2*k+1, l, (l+r)/2); tmp = max_segt_rec(t, a, b, 2*k+2, (l+r)/2, r); if (ans < tmp) { ans = tmp; } return ans; } int max_segt (int *t, int a, int b, int size) { return max_segt_rec(t, a, b, 0, 0, size); } int bin_search_segt (int *t, int a, int b, int k, int size) { return -1; } int main () { char s[200001] = ""; int res = 0; int len = 0; int z[200000] = {}; int size = 1; int tz[600000] = {}; int tm[600000] = {}; int idx1 = 1; int idx2 = 0; res = scanf("%s", s); while (s[len] != '\0') { len++; } while (size <= len) { size <<= 1; } for (int i = 0; i < len; i++) { set_segt(tm, i, -len, size); } z[0] = len; while (idx1 < len) { while (idx1+idx2 < len && s[idx2] == s[idx1+idx2]) { idx2++; } if (idx2 != 0) { int idx3 = 1; while (idx3 < idx2 && idx3+z[idx3] < idx2) { z[idx1+idx3] = z[idx3]; idx3++; } idx1 += idx3; idx2 -= idx3; } else { idx1++; } } for (int i = 0; i < len; i++) { set_segt(tz, i, z[i], size); } for (int i = 2; i <= len/2; i++) { int tmp_idx = bin_search_segt(tz, i, len, i, size); if (tmp_idx >= 0) { int tmp_cnt = (-1)*max_segt(tm, 0, i+1, size); tmp_cnt++; while (tmp_idx >= 0) { tmp_cnt -= i-1; if (tmp_cnt < (-1)*get_segt(tm, tmp_idx, size)) { set_segt(tm, tmp_idx, -tmp_cnt, size); } tmp_idx = bin_search_segt(tz, tmp_idx+i, len, i, size); } } } printf("%d\n", (-1)*max_segt(tm, 0, len, size)); return 0; }