SPOJ NSUBSTR Substrings

Description

You are given a string S which consists of 250000 lowercase latin letters at most. We define F(x) as the maximal number of times that some string with length x appears in S. For example for string 'ababa' F(3) will be 2 because there is a string 'aba' that occurs twice. Your task is to output F(i) for every i so that 1<=i<=|S|.

Input

String S consists of at most 250000 lowercase latin letters.

Output

Output |S| lines. On the i-th line output F(i).

Example

Input:

ababa

Output:

3

2

2

1

1

Hint

字尾自動機

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 300005;
char s[maxn];

class SAM
{
  const static int maxn = 500005;   //節點個數  
  const static int size = 26;     //字元的範圍  
  const static char base = 'a';     //字元的基準  

  class node
  {
  public:
    node *fa, *next[size];
    int len, cnt;
    node* clear(int x, int y)
    {
      fa = 0; len = x;
      cnt = y;
      memset(next, 0, sizeof(next));
      return this;
    }
    bool operator <(const node&x) const
    {
      return len < x.len;
    }
  }nd[maxn], *u[maxn];                     //節點的設定  

  node *root, *last;              //根節點,上一個節點  
  int tot, f[maxn];                        //總節點數  
public:
  void clear()
  {
    last = root = &nd[tot = 0];
    nd[0].clear(0, 0);
  }                               //初始化  
  void insert(char ch)
  {
    node *p = last, *np = nd[++tot].clear(p->len + 1, 1);
    last = np;
    int x = ch - base;
    while (p&&p->next[x] == 0) p->next[x] = np, p = p->fa;
    if (p == 0) { np->fa = root; return; }

    node* q = p->next[x];
    if (p->len + 1 == q->len) { np->fa = q; return; }

    node *nq = nd[++tot].clear(p->len + 1, 0);
    for (int i = 0; i < size; i++)
      if (q->next[i]) nq->next[i] = q->next[i];
    nq->fa = q->fa;
    q->fa = np->fa = nq;
    while (p &&p->next[x] == q) p->next[x] = nq, p = p->fa;
  }                               //插入操作  

  void query()
  {
    for (int i = 1; i <= tot; i++) f[i] = 0;
    for (int i = 1; i <= tot; i++) f[nd[i].len]++;
    for (int i = 1; i <= tot; i++) f[i] += f[i - 1];
    for (int i = 1; i <= tot; i++) u[f[nd[i].len]--] = &nd[i];
    for (int i = 1; i <= u[tot]->len + 1; i++) f[i] = 0;
    for (int i = tot; i; i--)
    {
      u[i]->fa->cnt += u[i]->cnt;
      f[u[i]->len] = max(f[u[i]->len], u[i]->cnt);
    }
    for (int i = u[tot]->len; i; i--) f[i] = max(f[i], f[i + 1]);
    for (int i = 1; i <= u[tot]->len; i++) printf("%d\n", f[i]);
  }
}sam;

int main()
{
  while (scanf("%s", s) != EOF)
  {
    sam.clear();
    for (int i = 0; s[i]; i++) sam.insert(s[i]);
    sam.query();
  }
  return 0;
}