    /**
     * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
     */

    #include <cassert>
    #include <cstring>

    #define forn(i, n) for (int i = 0; i < (int)(n); i++)

    template <const int N, const int ALPHA>
    struct Automaton {
      static const int VN = 2 * N + 1;
      int root, last, n, len[N], suf[N], next[N][ALPHA];

      inline int newV( int l, int _suf ) {
        assert(n < VN);
        memset(next[n], 0, sizeof(next[n]));
        len[n] = l, suf[n] = _suf;
        return n++;
      }
      void build( const char *s ) {
        forn(i, ALPHA)
          next[0][i] = 1;
        n = 1, root = last = newV(0, 0);
        for (int i = 0; s[i]; i++) {
          int ch = s[i] - 'a';
          int R, Q, P = last;
          last = newV(len[last] + 1, 0);
          while (!next[P][ch])
            next[P][ch] = last, P = suf[P];
          if (!P)
            suf[last] = 1;
          else if (len[Q = next[P][ch]] == len[P] + 1)
            suf[last] = Q;
          else {
            R = newV(len[P] + 1, suf[Q]);
            suf[last] = suf[Q] = R;
            memcpy(next[R], next[Q], sizeof(next[R]));
            while (P && next[P][ch] == Q)
              next[P][ch] = R, P = suf[P];
          }
        }
      }
    };

    Automaton<3> a;

    int main() {
      const char *s = "abc";
      a.build(s);
    }