Description

XX在进行字符串研究的时候，遇到了一个十分棘手的问题。

在这个问题中，给定一个字符串S，与一个整数K，定义S的子串T=S(i, j)是关于第K位的识别子串，满足以下两个条件：

1、i≤K≤j。

2、子串T只在S中出现过一次。

例如，S="banana"，K=5，则关于第K位的识别子串有"nana"，"anan"，"anana"，"nan"，"banan"和"banana"。

现在，给定S，XX希望知道对于S的每一位，最短的识别子串长度是多少，请你来帮助他。

Input

仅一行，输入长度为N的字符串S。

Output

输出N行，每行一个整数，第i行的整数表示对于第i位的最短识别子串长度。

Sample Input

agoodcookcooksgoodfood

Sample Output

1

2

3

3

2

2

3

3

2

2

3

3

2

1

2

3

3

2

1

2

3

4

HINT

N<=5*10^5

---

首先发现可以按照每个后缀统计贡献

然后直接把每个后缀和前后排名的串lcp的max:len求出来，这些值是不能更新的

然后对于$[i,i+len] \(用len+1更新，对于\)[i+len,n]$用一个等差数列更新min

等差数列维护直接标记永久化就可以了

然后注意特判是不是没有合法的解

---

#include
    
     using namespace std;typedef pair
     
       pi;const int N = 5e5 + 10;const int INF_of_int = 1e9;int typ1[N << 2], typ2[N << 2];#define LD (t << 1)#define RD (t << 1 | 1)void build(int t, int l, int r) {  typ1[t] = INF_of_int;  typ2[t] = -INF_of_int;  if (l == r) return;  int mid = (l + r) >> 1;  build(LD, l, mid);  build(RD, mid + 1, r);}void modify(int t, int l, int r, int ql, int qr, int typ, int val) {  if (ql > qr) return;  if (ql <= l && r <= qr) {    if (typ == 1) {      typ1[t] = min(typ1[t], val);    } else {      typ2[t] = max(typ2[t], val);    }    return;  }  int mid = (l + r) >> 1;  if (qr <= mid) modify(LD, l, mid, ql, qr, typ, val);  else if (ql > mid) modify(RD, mid + 1, r, ql, qr, typ, val);  else {    modify(LD, l, mid, ql, mid, typ, val);    modify(RD, mid + 1, r, mid + 1, qr, typ, val);  }} void output(int t, int l, int r, int val, int pos) {  if (typ1[t]) val = min(val, typ1[t]);  if (typ2[t]) val = min(val, pos - typ2[t] + 1);  if (l == r) {    printf("%d\n", val);    return;  }  int mid = (l + r) >> 1;  if (pos <= mid) output(LD, l, mid, val, pos);  else output(RD, mid + 1, r, val, pos); }struct Suffix_Array {  int s[N], n, m;  int c[N], x[N], y[N];  int sa[N], rank[N], height[N];    void init(int len, char *c) {    n = len, m = 0;    for (int i = 1; i <= n; i++) {      s[i] = c[i];      m = max(m, s[i]);    }   }    void radix_sort() {    for (int i = 1; i <= m; i++) c[i] = 0;    for (int i = 1; i <= n; i++) c[x[y[i]]]++;    for (int i = 1; i <= m; i++) c[i] += c[i - 1];    for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i];  }    void buildsa() {    for (int i = 1; i <= n; i++) x[i] = s[i], y[i] = i;    radix_sort();    int now;    for (int k = 1; k <= n; k <<= 1) {      now = 0;      for (int i = n - k + 1; i <= n; i++) y[++now] = i;      for (int i = 1; i <= n; i++) if (sa[i] > k) y[++now] = sa[i] - k;      radix_sort();      y[sa[1]] = now = 1;      for (int i = 2; i <= n; i++) y[sa[i]] = (x[sa[i]] == x[sa[i - 1]] && x[sa[i] + k] == x[sa[i - 1] + k]) ? now : ++now;      swap(x, y);      if (now == n) break;      m = now;     }  }    void buildrank() {    for (int i = 1; i <= n; i++) rank[sa[i]] = i;  }    void buildheight() {    for (int i = 1; i <= n; i++) {      int k = max(height[rank[i - 1]] - 1, 0);      for (; s[i + k] == s[sa[rank[i] - 1] + k]; k++);      height[rank[i]] = k;    }  }    void build(int len, char *c) {    init(len, c);    buildsa();    buildrank();    buildheight();  }     void solve() {    for (int i = 1; i <= n; i++) {      int len = max(height[rank[i]], height[rank[i] + 1]);      if (i + len > n) continue;      modify(1, 1, n, i, i + len, 1, len + 1);      modify(1, 1, n, i + len, n, 2, i);    }  }} Sa;int len;char s[N];int main() {#ifdef dream_maker  freopen("input.txt", "r", stdin);#endif  scanf("%s", s + 1);  len = strlen(s + 1);  Sa.build(len, s);  build(1, 1, len);  Sa.solve();  for (int i = 1; i <= len; i++) output(1, 1, len, len, i);  return 0;}