// authors: F. Franek and H. Koponen

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int _cek;
#define done() { printf("\n<enter> to terminate\n"); _cek = getchar(); exit(0); }

void show_substring(const char* string, int from, int to, const char* trm = "\n") {
  for (int i = from; i <= to; i++)
    putchar(string[i]);
  printf("%s", trm);
}

class MyString {
public:
  char* string;
  int len;
  MyString* next, * prev;
  int roti; // only used for phi, rho
  int rank; // only used for phi, rho

  MyString(const char* u, int from, int to) {
    len = to - from + 1;
    string = new char[len + 1];
    for (int i = from; i <= to; i++)
      string[i - from] = u[i];
    string[len] = '\0';
    rank = roti = 0;
    next = prev = 0;
  }

  MyString(const char* u) {
    len = (int)strlen(u);
    string = new char[len + 1];
    strcpy(string, u);
    rank = roti = 0;
    next = prev = 0;
  }

  MyString(MyString* u) {
    len = u->len;
    string = new char[len + 1];
    strcpy(string, u->string);
    rank = roti = 0;
    next = prev = 0;
  }

  MyString(MyString* u, int from, int to) {
    len = to - from + 1;
    string = new char[len + 1];
    for (int i = from; i <= to; i++)
      string[i - from] = u->string[i];
    string[len] = '\0';
    rank = roti = 0;
    next = prev = 0;
  }

  ~MyString() {
    if (string)
      delete[] string;
  }

  void show(const char* trm = "\n") {
    printf("%s%s", string, trm);
  }

  static int cmp(MyString* v1,MyString* v2) {
    return(strcmp(v1->string, v2->string));
  }


  // returns -1 if s1 and s2 are not conjugates
  // returns j>=0 such that rot(s1,j)=s2
  static int conjugates(const char* string, int from1, int to1, int from2, int to2) {
    int s1len = to1-from1+1;
    int s2len = to2-from2+1;
    if (s1len != s2len)
      return -1;
    int i, j, l = s1len;
    bool found;
    for (i = 0; i < l; i++) {
      found = true;
      for (j = 0; j < l; j++) {
        if (j + i < l) {
          if (string[from1+j + i] != string[from2+j]) {
            found = false;
            break;
          }
        }
        else {
          if (string[from1+j + i - l] != string[from2+j]) {
            found = false;
            break;
          }
        }
      }
      if (found)
        return j;
    }
    return -1;
  }

  static int conjugates(const char* s1, const char* s2) {
    int s1len = (int)strlen(s1);
    int s2len = (int)strlen(s2);
    if (s1len != s2len)
      return -1;
    int i, j, l = s1len;
    bool found;
    for (i = 0; i < l; i++) {
      found = true;
      for (j = 0; j < l; j++) {
        if (j + i < l) {
          if (s1[j + i] != s2[j]) {
            found = false;
            break;
          }
        }
        else {
          if (s1[j + i - l] != s2[j]) {
            found = false;
            break;
          }
        }
      }
      if (found)
        return j;
    }
    return -1;
  }

  static int conjugates(MyString* s1, MyString* s2) {
    if (s1->len != s2->len)
      return -1;
    int i, j, l = s1->len;
    bool found;
    for (i = 0; i < l; i++) {
      found = true;
      for (j = 0; j < l; j++) {
        if (j + i < l) {
          if (s1->string[j + i] != s2->string[j]) {
            found = false;
            break;
          }
        }
        else {
          if (s1->string[j + i - l] != s2->string[j]) {
            found = false;
            break;
          }
        }
      }
      if (found)
        return j;
    }
    return -1;
  }


  static int conjugates(MyString* s1, const char* string, int from, int to) {
    int s2len = to - from + 1;
    if (s1->len != s2len)
      return -1;
    int i, j, l = s1->len;
    bool found;
    for (i = 0; i < l; i++) {
      found = true;
      for (j = 0; j < l; j++) {
        if (j + i < l) {
          if (s1->string[j + i] != string[from+j]) {
            found = false;
            break;
          }
        }
        else {
          if (s1->string[j + i - l] != string[from+j]) {
            found = false;
            break;
          }
        }
      }
      if (found)
        return j;
    }
    return -1;
  }
};//end class MyString


class MyStringSet {
public:
  MyString * start, *end;
  int setlen;

  MyStringSet() {
    start = end = 0;
    setlen = 0;
  }

  MyStringSet(MyStringSet* s) {
    start = end = 0;
    for (MyString* t = s->start; t != 0; t = t->next) {
      insert(t);
    }
  }

  ~MyStringSet() {
    MyString* p, * q;
    if (start) {
      p = start;
      while (true) {
        q = p->next;
        delete p;
        if (q == 0)
          break;
        p = q;
      }
    }
  }

  void show(const char* trm = "\n") {
    for (MyString* p = start; p != 0; p = p->next)
      p->show();
    printf("%s", trm);
  }

  void show_with_rank(const char* trm = "\n") {
    if (start->rank == 0)
      rankify();
    for (MyString* p = start; p != 0; p = p->next) {
      printf("rank %d: ", p->rank);
      p->show();
    }
  }

  void insert(const char* u,int from,int to) {
    int k;
    MyString *t, *p, *q;
    if (start == 0) {
      end = start = new MyString(u,from,to);
      setlen++;
      return;
    }
    k = strncmp(&u[from], start->string,to-from+1);
    if (k == 0)
      return;
    if (k < 0) {
      t = new MyString(u, from, to);
      t->next = start;
      start->prev = t;
      start = t;
      setlen++;
      return;
    }
    if (start->next == 0) {
      start->next = new MyString(u, from, to);
      start->next->prev = start;
      setlen++;
      return;
    }
    p = start;
    q = start->next; 
    while (true) {
      k = strncmp(&u[from], q->string, to - from + 1);
      if (k == 0)
        return;
      if (k < 0) {
        t = new MyString(u,from,to);
        p->next = t;
        t->prev = p;
        t->next = q;
        if (q != 0)
          q->prev = t;
        setlen++;
        return;
      }
      p = q;
      q = q->next;
      if (q == 0)
        break;
    }
    t = new MyString(u,from,to);
    p->next = t;
    t->prev = p;
    setlen++;
    end = t;
  }

  void insert(const char* u) {
    int len = (int)strlen(u);
    insert(u, 0, len-1);
  }

  void insert(MyString* u, int from, int to) { 
    insert(u->string, from, to);
  }
  void insert(MyString* u) { 
    insert(u->string,0, u->len-1); 
  }

  void append(MyString* u) {
    if (start == 0) {
      end = start = new MyString(u);
      return;
    }
    else {
      end->next = new MyString(u);
      end->next->prev = end;
      end = end->next;
      return;
    }
  }

  void append(const char* u,int from, int to,int roti = 0) {
    if (start == 0) {
      end = start = new MyString(u, from, to);
      return;
    }
    else {
      end->next = new MyString(u, from, to);
      end->next->prev = end;
      end = end->next;
      return;
    }
  }

  void emptyit() {
    MyString* p, * q;
    if (start) {
      p = start;
      while (true) {
        q = p->next;
        delete p;
        if (q == 0)
          break;
        else
          p = q;
      }
      start = 0;
    }
    setlen = 0;
  }

  void mark(const char* u, int from, int to) {
    MyString* p;
    if (start == 0)
      return;
    int len = to - from + 1;
    for (p = start; p != 0; p = p->next) {
      if (strncmp(p->string, &u[from], len) != 0)
        continue;
      //it is this element, mark it
      p->roti = 1;
      return;
    }
  }

  // it is assumed that for this set, roti was calculated
  void reorder_by_roti() {
    int i, stop;
    MyString *q, *p;
    if (setlen < 2)
      return;
    MyString** array = new MyString * [setlen];
    for (i = 0; i < setlen; array[i++] = 0);
    start->roti = 0;
    array[0] = start;
    i = 1;
    for (q = start->next; q != 0; q = q->next, i++) {
      q->roti = MyString::conjugates(start, q);
      array[i] = q;
    }

    // now sort array by roti
    for (stop = setlen - 1; stop > 0; stop--) {
      for (i = 0; i < stop; i++) {
        if (array[i]->roti > array[i + 1]->roti) {
          p = array[i];
          array[i] = array[i + 1];
          array[i + 1] = p;
        }
      }
    }

    // remake the set by array
    q = start = array[0];
    for (i = 1; i < setlen; i++) {
      array[i]->prev = q;
      array[i]->next = 0;
      q->next = array[i];
      q = array[i];
    }
    delete[] array;
  }

  // compute rank
  void rankify() {
    int i = 1;
    for (MyString* q = start; q != 0; q = q->next)
      q->rank = i++;
  }
};//end class MyStringSet



class PathNode {
public:
  MyString* arc;
  PathNode* next, * prev;
  PathNode(MyString* u) {
    arc = new MyString(u);
    next = prev = 0;
  }
  PathNode(PathNode* p) {
    arc = new MyString(p->arc);
    next = prev = 0;
  }
  ~PathNode() {
    if (arc) delete arc;
  }
};//end class PathNode

class Path {
public:
  int len;
  PathNode* start, * end;
  Path() {
    len = 0;
    start = end = 0;
  }
  Path(Path* p) {
    PathNode* c;
    len = p->len;
    for (PathNode* s = p->start; s != 0; s = s->next) {
      if (start == 0) {
        end = start = new PathNode(s);
      }
      else {
        c = new PathNode(s);
        end->next = c;
        c->prev = end;
        end = c;
      }
    }
  }
  ~Path() {
    PathNode* p, * q;
    if (start == 0)
      return;
    if (start->next == 0) {
      delete start;
      start = 0;
      len = 0;
    }
    p = start;
    q = start->next;
    while (true) {
      delete p;
      if (q == 0)
        return;
      p = q;
      q = q->next;
    }
  }
  void append(MyString* u) {
    if (start == 0) {
      start = end = new PathNode(u);
      len++;
      return;
    }
    else {
      end->next = new PathNode(u);
      len++;
      end->next->prev = end;
      end = end->next;
    }
  }

  void remove_last() {
    PathNode* p;
    if (start == 0)
      return;
    if (start == end) {
      delete start;
      len = 0;
      start = end = 0;
      return;
    }
    p = end;
    end = end->prev;
    end->next = 0;
    len--;
    delete p;
    return;
  }

  void empty_all() {
    PathNode* p, * q;
    if (start == 0)
      return;
    if (start == end) {
      delete start;
      len = 0;
      start = end = 0;
      return;
    }
    p = start;
    q = start->next;
    while (true) {
      delete p;
      len--;
      if (q == 0)
        break;
      p = q;
      q = q->next;
    }
  }

  void show(const char* trm = "\n") {
    for (PathNode* p = start; p != 0; p = p->next) {
      for (int i = 0; i < p->arc->len - 1; i++)
        putchar(p->arc->string[i]);
      printf(" -%s-> %s\n", p->arc->string, &(p->arc->string[1]));
    }
    printf("%s", trm);
  }

  bool is_cycle() {
    MyString* s1 = start->arc;
    MyString* s2 = end->arc;
    int k = strncmp(s1->string, &(s2->string[1]), s1->len - 1);
    if (k == 0)
      return true;
    else
      return false;
  }

  static bool are_equivalen(Path* p1, Path* p2) {
    if (p1->len != p2->len)
      return false;
    int i, l = p1->len;
    bool found_diff;
    PathNode* pn1, * kn1, * kn2;
    for (pn1 = p1->start; pn1 != 0; pn1 = pn1->next) {
      found_diff = false;
      i = 0;
      kn1 = pn1;
      kn2 = p2->start;
      while (true) {
        if (strcmp(kn1->arc->string, kn2->arc->string) != 0) {
          found_diff = true;
          break;
        }
        if (kn1->next != 0)
          kn1 = kn1->next;
        kn2 = kn2->next;
      }
      if (found_diff)
        continue;
      else
        break;
    }
    return true;
  }

  bool contains(MyString* u) {
    for (PathNode* p = start; p != 0; p = p->next) {
      if (strcmp(p->arc->string, u->string) == 0)
        return true;
    }
    return false;
  }
};//end class Path


class CyclesNode {
public:
  Path* path;
  CyclesNode* cnext, * cprev;

  CyclesNode() {
    cnext = cprev = 0;
  }

  CyclesNode(Path* t) {
    path = new Path(t);
    cnext = cprev = 0;
  }

  ~CyclesNode() {
    if (path)
      delete path;
  }

  void show(const char* trm = "\n") {
    if (path)
      path->show(trm);
  }
};//end class CyclesNode



class Cycles {
public:
  CyclesNode* cstart, * cend;
  int clen;

  Cycles() { cstart = cend = 0; clen = 0;  }

  ~Cycles() {
    if (cstart == 0)
      return;
    if (cstart->cnext == 0) {
      delete cstart;
      return;
    }
    CyclesNode* p, * q;
    p = cstart;
    q = cstart->cnext;
    while (true) {
      delete p;
      clen--;
      if (q == 0)
        return;
      p = q;
      q = q->cnext;
    }
  }

  void append(Path* p) {
    CyclesNode* c;
    if (cstart == 0) {
      cend = cstart = new CyclesNode(p);
      clen = 1;
      return;
    }
    // is it equivalent to some previous cycle?
    for (c = cstart; c != 0; c = c->cnext) {
      if (Path::are_equivalen(c->path, p))
        return;
    }
    // so it is a new cycle
    c = new CyclesNode(p);
    cend->cnext = c;
    c->cprev = cend;
    cend = c;
    clen++;
  }

  void show(const char* trm = "\n") {
    for (CyclesNode* p = cstart; p != 0; p = p->cnext) {
      p->show(trm);
    }
  }
};//end class Cycles



class Rauzy {
public:
  char* string;
  int len;
  MyStringSet** R;
  Cycles** CA;
  bool cycles_computed;

  Rauzy(const char* u) {
    len = (int)strlen(u);
    string = new char[len + 1];
    strcpy(string, u);
    R = new MyStringSet * [len];
    for (int i = 0; i < len; i++)
      R[i] = new MyStringSet();
    for (int i = 0; i < len; i++) {
      for (int j = 0; j + i < len; j++)
        R[i]->insert(string, j, j + i);
    }
    CA = new Cycles * [len];
    for (int i = 0; i < len; CA[i++] = 0);
    cycles_computed = false;
  }

  ~Rauzy() {
    if (string) delete[] string;
    if (R) {
      for (int i = 0; i < len; i++)
        if (R[i]) delete R[i];
      delete[] R;
    }
    if (CA) {
      for (int i = 0; i < len; i++)
        if (CA[i]) delete CA[i];
      delete[] CA;
    }
  }


  void show_graph(const char* trm = "\n") {
    printf("Ruazy graph for string %s\n", string);
    for (int i = 0; i < len; i++) {
      // R[i] are vertices, R[i+1] are arcs
      printf("R%d:\n", i + 1);
      if (i == len - 1) {
        printf("no arcs\n");
        printf("isolated vertices: %s\n", string);
        printf("-------------------------------\n");
        return;
      }
      for (MyString* arc = R[i + 1]->start; arc != 0; arc = arc->next) {
        for (int j = 0; j <= i; j++)
          putchar(arc->string[j]);
        printf(" -%s-> %s\n", arc->string, &(arc->string[1]));
      }
      printf("-------------------------------\n");
    }
  }

  void emptyit() {
    for (int i = 0; i < len; i++)
      if (R[i]) {
        R[i]->emptyit();
        R[i] = 0;
      }
  }

  static void compute_cycles_comp1(MyStringSet* E, Path* p, Cycles* C) {
    MyString* e;
    for (e = E->start; e != 0; e = e->next) {
      if (p->contains(e)) { // e is already on the Path p
        continue;
      }
      // so Path p does not contain e
      // can e extend end ?
      if (strncmp(&(p->end->arc->string[1]), e->string, e->len - 1) != 0) { // NO
        continue;
      }
      else {                                                               // YES
        p->append(e);
        if (p->is_cycle()) {
          C->append(p);
          p->remove_last();
          continue;
        }
        else {
          compute_cycles_comp1(E, p, C);
          p->remove_last();
          continue;
        }
      }
    }
  }

  static Cycles* compute_cycles_comp(MyStringSet* E) {
    Cycles* C = new Cycles();
    Path* p = new Path();
    MyString* e;
    for (e = E->start; e != 0; e = e->next) {
      p->append(e);
      compute_cycles_comp1(E, p, C);
      p->empty_all();
    }
    return C;
  }

  void compute_cycles_all() {
    if (cycles_computed)
      return;
    for (int i = 0; i < len - 1; i++)
      CA[i] = compute_cycles_comp(R[i + 1]);
  }

  void show_cycles(int i, const char* trm = "\n") {
    int clen;
    if (!cycles_computed)
      compute_cycles_all();
    if (CA[i] == 0)
      clen = 0;
    else
      clen = CA[i]->clen;
    printf("R[%d]: number of cycles %d\n", i+1,clen);
    if (i == len - 1 || clen == 0)
      return;
    CA[i]->show();
  }

  void show_cycles(const char* trm = "\n") {
    if (!cycles_computed)
      compute_cycles_all();
    for (int i = 0; i < len; i++)
      show_cycles(i, trm);
  }
};//end class Rauzy


class SquareNode {
public:
  MyString* master_string;
  int s, p; // start, period
  SquareNode* next, * prev;

  SquareNode(MyString* master_string, int s, int p) {
    this->master_string = master_string;
    this->s = s;
    this->p = p;
    next = prev = 0;
  }

  void show_square(const char* trm = "\n") {
    for (int i = s; i < s+2*p; i++)
      putchar(master_string->string[i]);
    printf("%s", trm);
  }

  void show_root(const char* trm = "\n") {
    for (int i = s; i < i + p; i++)
      putchar(master_string->string[i]);
    printf("%s", trm);
  }
};//end class SquareNode


class Squares {
public:
  static MyString* master_string;
  SquareNode* start, * end;
  int len;

  Squares(const char* ms) {
    master_string = new MyString(ms);
    start = end = 0;
    len = 0;
    compute_squares();
  }

  Squares(MyString* ms) {
    master_string = new MyString(ms);
    start = end = 0;
    len = 0;
    compute_squares();
  }

  void insert_new_square(int s, int p) {
    SquareNode* w1, * w2;
    if (start == 0) {
      start = new SquareNode(master_string, s, p);
      len = 1;
      return;
    }
    if (p < start->p || (p == start->p && s < start->s)) {
      w1 = new SquareNode(master_string, s, p);
      w1->next = start;
      start->prev = w1;
      start = w1;
      len++;
      return;
    }
    if (start->next == 0) {
      w1 = new SquareNode(master_string, s, p);
      start->next = w1;
      w1->prev = start;
      end = w1;
      len++;
      return;
    }
    w1 = start;
    w2 = start->next;
    while (true) {
      if (p < w2->p || (p == w2->p && s < w2->s)) {
        w1->next = new SquareNode(master_string, s, p);
        w1->next->prev = w1;
        w1->next->next = w2;
        w2->prev = w1->next;
        len++;
        return;
      }
      w1 = w2;
      w2 = w2->next;
      if (w2 == 0) {
        end = new SquareNode(master_string, s, p);
        w1->next = end;
        end->prev = w1;
        len++;
        return;
      }
    }
  }

  bool is_square(int s, int p) {
    for (int i = s; i < s + p; i++) {
      if (master_string->string[i] != master_string->string[i + p])
        return false;
    }
    return true;
  }

  void compute_squares() {
    int p; // period of square
    int s; // start of square
    for (p = 1; p <= master_string->len / 2; p++) {
      for (s = 0; s + 2 * p <= master_string->len; s++) {
        if (is_square(s, p))
          insert_new_square(s, p);
      }
    }
  }

  ~Squares() {
    if (master_string)
      delete master_string;
    master_string = 0;
  }

  void show(const char* trm = "\n") {
    printf("%s\n", master_string->string);
    int n = master_string->len;
    for (SquareNode* q = start; q != 0; q = q->next) {
      for (int i = 0; i < n; i++) {
        if (i < q->s) {
          putchar('.');
        }
        else if (q->s <= i && i < q->s + 2 * q->p) {
          putchar(master_string->string[i]);
        }
        else
          putchar('.');
      }
      putchar('\n');
    }
  }

  MyStringSet** roots(int p,int& iV) {
    // prepare up to len many MyStringSets
    MyStringSet** V = new MyStringSet * [len];
    for (int i = 0; i < len; V[i++] = 0);

    iV = 0;
    int are_conjugates;
    bool found;
    // this eliminates duplicates and orders them lexicographically
    for (SquareNode* q = start; q != NULL; q = q->next) {
      if (q->p == p) {
        if (V[iV] == 0) {
          V[iV] = new MyStringSet();
          V[iV]->insert(q->master_string, q->s, q->s + p - 1);
        }
        else {
          found = false;
          for (int i = 0; i <= iV; i++) {
            are_conjugates = MyString::conjugates(V[i]->start, q->master_string->string, q->s, q->s + q->p - 1);
            if (are_conjugates < 0) {
              // not to go into this existing set
              continue;
            }
            else {
              // it goes into this existing set
              V[i]->insert(q->master_string, q->s, q->s + q->p - 1);
              found = true;
              break;
            }
          }
          if (!found) {
            // must create a new set
            iV++;
            V[iV] = new MyStringSet();
            V[iV]->insert(q->master_string->string, q->s, q->s + q->p - 1);
          }
        }
      }
    }

    // so we have 0..iV many sets 
    // reorder each set by roti
    for (int i = 0; i <= iV; i++)
      V[i]->reorder_by_roti();

    //change roti to rank
    for (int i = 0; i <= iV; i++)
      V[i]->rankify();
    return V;
  }

  static MyString* rho(MyString* v,int r, int t) {
    // r:  1..len
    // t:  0..len-1
    if (r < 1 || r > v->len) {
      printf("rho: incorrect parameter r=%d\n", r);
      done()
    }
    if (t < 0 || t >= v->len) {
      printf("rho: incorrect parameter t=%d\n", t);
      done()
    }
    int p = v->len;
    char* u = new char[p + r + 1];
    if (t + r <= p) {
      strcpy(u, &(v->string[t]));
      strncat(u, v->string, t + r);
      if (strlen(u) != p + r) {
        printf("error 1\n");
        done()
      }
    }
    else {
      strcpy(u, &(v->string[t]));
      strcat(u, v->string);
      strncat(u, v->string, t + r - p);
      if (strlen(u) != p + r) {
        printf("error 2\n");
        done()
      }
    }
    MyString* w = new MyString(u);
    delete[] u;
    return w;
  }

  // it is assumed that it had rank assigned
  static MyStringSet* phi(MyString* leader,MyString* u,bool showit=false) {
    if (u->rank < 1) {
      printf("phi error 1\n");
      done()
    }
    if (leader->rank < 1) {
      printf("phi error 2\n");
      done()
    }
    if (leader->len != u->len) {
      printf("phi error 3\n");
      done()
    }
    if (strcmp(u->string, leader->string) < 0) {
      printf("phi error 4\n");
      done()
    }

    MyStringSet* v = new MyStringSet();
    for (int t = 0; t < u->len; t++)
      v->insert(rho(leader,u->rank, t));

    if (showit) {
      printf("phi(%s%s)=(", u->string, u->string);
      for (MyString* w = v->start; w != 0; w = w->next)
        if (w->next == 0)
          printf("%s)\n", w->string);
        else
          printf("%s,", w->string);
    }
    return v;
  }
};//end class Squares
MyString* Squares::master_string;


// check wether uu is a substring of v
bool substring_test(const char* u, const char* v) {
  int p = (int)strlen(u); // size of u
  int P = (int)strlen(v); // size of v
  int l = P - p;
  for (int i = 0; i <= l; i++) {
    if (strncmp(&v[i], u, p) != 0)
      continue;
    else
      return true;
  }
  return false;
}

int main() {
  char u[] = "cabcabxabcabcxbcxbcabca";
  Rauzy* RA = new Rauzy(u);
  //RA->show_graph();
  //RA->show_cycles();
  Squares* SA = new Squares(u);
  SA->show();

  int iV;
  MyStringSet** RO = SA->roots(3, iV);
  MyStringSet* ph;
  for (int i = 0; i <= iV; i++) {
    printf("list ordered roots:\n");
    RO[i]->show_with_rank();
    printf("list phi() of al the ordered roots:\n");
    for (MyString* w = RO[i]->start; w != 0; w = w->next) {
      ph = Squares::phi(RO[i]->start, w, true);
      for (MyString* x = ph->start; x != 0; x = x->next) {
        if (!substring_test(x->string, u)) {
          printf("phi sequence error\n");
          done()
        }
      }
    }
  }

  delete RA;
  delete SA;
  for (int i = 0; i <= iV; i++)
    delete RO[i];
  delete[] RO;
  done()
  return 0;
}