/**
 * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
 * (translated from C++ by Pavel Mavrin)
 */

class SuffixAutomaton {

    public static final int ALPHA_SIZE = 27;
    public int root, last, n;
    public final int len[], suf[], next[];

    public SuffixAutomaton(String s) {
        len = new int[2 * s.length() + 2];
        suf = new int[2 * s.length() + 2];
        //compressed 2d array. next[i][j] -> next[i * ALPHA_SIZE + j];
        next = new int[(2 * s.length() + 2) * ALPHA_SIZE];
        for (int i = 0; i < ALPHA_SIZE; i++)
            next[i] = 1;
        n = 1;
        root = last = newV(0, 0);
        for (int i = 0; i < s.length(); i++) {
            int ch = s.charAt(i) - 'a';
            int R, Q, P = last;
            last = newV(len[last] + 1, 0);
            while (next[P * ALPHA_SIZE + ch] == 0) {
                next[P * ALPHA_SIZE + ch] = last;
                P = suf[P];
            }
            if (P == 0)
                suf[last] = 1;
            else if (len[Q = next[P * ALPHA_SIZE + ch]] == len[P] + 1)
                suf[last] = Q;
            else {
                R = newV(len[P] + 1, suf[Q]);
                suf[last] = suf[Q] = R;
                System.arraycopy(next, Q * ALPHA_SIZE, next, R * ALPHA_SIZE, ALPHA_SIZE);
                while (P > 0 && next[P * ALPHA_SIZE + ch] == Q) {
                    next[P * ALPHA_SIZE + ch] = R;
                    P = suf[P];
                }
            }
        }
    }

    private int newV(int l, int _suf) {
        if ((n >= len.length)) throw new AssertionError();
        for (int i = 0; i < ALPHA_SIZE; i++) {
            next[n * ALPHA_SIZE + i] = 0;
        }
        len[n] = l;
        suf[n] = _suf;
        return n++;
    }
}