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