{

node *next[ALPHABET_SIZE], *parent;

int len;

node(int _len = 0) : len(_len) { memset(next, 0, sizeof(next)), parent = NIL; }

{

root = new node(0);

last = root;

{

node *p = last;

node *np = new node(p->len + 1);

while (p != NIL && p->next[x] == NIL)

{

p->next[x] = np;

p = p->parent;

}

if (p == NIL)

{

np->parent = root;

}

else

{

node *q = p->next[x];

if (q->len == p->len + 1)

{

np->parent = q;

}

else

{

node *nq = new node;

*nq = *q;

nq->len = p->len + 1;

q->parent = np->parent = nq;

while (p != NIL && p->next[x] == q)

{

p->next[x] = nq;

p = p->parent;

}

}

}

last = np;

{

scanf("%s", s);

len = strlen(s);

init();

for (int i = 0; i < len; i++)

{

extend(s[i] - 'a');

}

return 0;