#ifndef SKIP
#include <cstdio>
#include <cstdlib>
#include <list>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <set>
using namespace std;
#endif

#ifndef MAP
#define MAP unordered_map
#endif

struct state
{
  /* Position of the state in the list of states.  */
  list<state>::iterator position;

  /* The parent state in the position tree.  */
  state *parent;

  /* The length of the longest string represented by this state
     (all other strings represented by this state are its suffixes,
     the shortest one of them has length parent.length + 1).  */
  int length;

  /* The transition function.  */
  MAP<char, state *> fwd;

  /* Id of the state.  */
  int id;
};

struct suffix_automaton
{
  /* States in this list are ordered so that all transitions are forward
     in the list and the parrent links go backwards.  */
  list<state> states;

  state *new_state (list<state>::iterator before)
    {
      list<state>::iterator pos = states.insert (before, state ());
      pos->position = pos;
      return &*pos;
    }

  suffix_automaton (const string &s)
    {
      state *init = new_state (states.end ());
      init->parent = NULL;
      init->length = 0;
      for (char c : s)
	add (c);
    }

  state *root_state (void)
    {
      return &states.front ();
    }

  state *final_state (void)
    {
      return &states.back ();
    }

  void add (int c)
    {
      state *p = final_state ();
      state *fin = new_state (states.end ());
      fin->length = p->length + 1;

      while (p && p->fwd.count (c) == 0)
	{
	  p->fwd[c] = fin;;
	  p = p->parent;
	}
      if (!p)
	{
	  fin->parent = root_state ();
	  return;
	}

      state *q = p->fwd[c];
      if (q->length == p->length + 1)
	{
	  fin->parent = q;
	  return;
	}

      state *split_q = new_state (q->position);
      split_q->fwd = q->fwd;
      split_q->length = p->length + 1;
      split_q->parent = q->parent;
      fin->parent = split_q;
      q->parent = split_q;
      split_q->fwd = q->fwd;

      while (p && p->fwd[c] == q)
	{
	  p->fwd[c] = split_q;
	  p = p->parent;
	}
    }

  int assign_ids (vector<state *> &id_to_state)
    {
      int id = 0;
      for (state &s : states)
	{
	  s.id = id++;
	  id_to_state.push_back (&s);
	}

      return id;
    }

  void dump (const string &wrto)
    { 
      vector<state *> id_to_state;
      int nstates = assign_ids (id_to_state);

      vector<int> pos (nstates);
      vector<set<int> > posset (nstates);
      state *s = root_state ();
      int n = final_state ()->length;
      for (int p = 0; p < n; p++)
	{
	  s = s->fwd[wrto[p]];
	  pos[s->id] = p;
	  posset[s->id].insert (p);
	}
      for (int x = nstates - 1; x > 0; x--)
	{
	  s = id_to_state[x];
	  state *p = s->parent;
	  pos[p->id] = pos[x];
	  posset[p->id].insert (posset[x].begin (), posset[x].end ());
	}

      for (state &s : states)
	{
	  printf ("State %d:\n", s.id);
	  if (s.length == 0)
	    printf ("  initial state\n");
	  else
	    {
	      string repr = wrto.substr (pos[s.id] - s.length + 1, s.length);
	      string sh = repr;
	      for (int i = 0; i < s.length - s.parent->length - 1; i++)
		sh[i] = ' ';
	      printf ("   parent state %d\n", s.parent->id);
	      printf ("   representative %s\n", repr.c_str ());
	      printf ("            up to %s\n", sh.c_str ());
	    }
	  printf ("   ends at");
	  for (int p : posset[s.id])
	    printf (" %d", p);
	  printf ("\n");
	  for (auto i = s.fwd.begin (); i != s.fwd.end (); ++i)
	    printf ("   '%c' -> %d\n", i->first, i->second->id);
	}
    }
};

#ifndef SKIP
int main (void)
{
  string s ("aaaaaa");
  suffix_automaton aut(s);
  aut.dump (s);
  return 0;
};
#endif