    /**
     * 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++;
        }
    }