// from https://gist.github.com/bicepjai/3355993#file-gistfile1-java-L147

/*

 * Copyright (c) 2016 Sergey Makagonov

 * 

 * Permission is hereby granted, free of charge, to any person obtaining

 * a copy of this software and associated documentation files (the

 * "Software"), to deal in the Software without restriction, including

 * without limitation the rights to use, copy, modify, merge, publish,

 * distribute, sublicense, and/or sell copies of the Software, and to

 * permit persons to whom the Software is furnished to do so, subject to

 * the following conditions:

 * 

 * The above copyright notice and this permission notice shall be

 * included in all copies or substantial portions of the Software.

 * 

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,

 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF

 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND

 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE

 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION

 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION

 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

 * 

 */

sclass UkkonenIntSuffixTree {

  Node[] nodes;

  int[] text;

  int root, position = -1, currentNode, needSuffixLink, remainder;

  int active_node, active_length, active_edge;

  static final int oo = Integer.MAX_VALUE/2; // TODO: Why /2?

  Comparator<Int> childComparator = (a, b) -> nodes[a].firstCharOrMinus1(this)-nodes[b].firstCharOrMinus1(this);

  sclass Node {

    int start, end = oo, link;

    public CompactTreeSet<Int> next = new(childComparator());

    *(int *start, int *end) {}

    public int edgeLength(UkkonenSuffixTree tree) {

      ret Math.min(end, tree.position + 1) - start;

    }

    CompactTreeSet<Int> makeEmptyChildrenSet(UkkonenIntSuffixTree tree) {

      ret new CompactTreeSet<>(tree.childComparator);

    }

    public int firstCharOrMinus1(IntSuffixTree tree) {

      ret tree.fullText[from);

    }

  }

  *(int length) {

    nodes = new Node[2*length+2];

    text = new char[length];

    root = active_node = newNode(-1, -1);

  }

  private void addSuffixLink(int node) {

      if (needSuffixLink > 0)

          nodes[needSuffixLink].link = node;

      needSuffixLink = node;

  }

  char active_edge() {

      return text[active_edge];

  }

  boolean walkDown(int next) {

      if (active_length >= nodes[next].edgeLength(this)) {

          active_edge += nodes[next].edgeLength(this);

          active_length -= nodes[next].edgeLength(this);

          active_node = next;

          return true;

      }

      return false;

  }

  int newNode(int start, int end) {

      nodes[++currentNode] = new Node(start, end);

      return currentNode;

  }

  public void addChar(char c) {

      text[++position] = c;

      needSuffixLink = -1;

      remainder++;

      while(remainder > 0) {

          if (active_length == 0) active_edge = position;

          if (!nodes[active_node].next.containsKey(active_edge())){

              int leaf = newNode(position, oo);

              nodes[active_node].next.put(active_edge(), leaf);

              addSuffixLink(active_node); //rule 2

          } else {

              int next = nodes[active_node].next.get(active_edge());

              if (walkDown(next)) continue;   //observation 2

              if (text[nodes[next].start + active_length] == c) { //observation 1

                  active_length++;

                  addSuffixLink(active_node); // observation 3

                  break;

              }

              int split = newNode(nodes[next].start, nodes[next].start + active_length);

              nodes[active_node].next.put(active_edge(), split);

              int leaf = newNode(position, oo);

              nodes[split].next.put(c, leaf);

              nodes[next].start += active_length;

              nodes[split].next.put(text[nodes[next].start], next);

              addSuffixLink(split); //rule 2

          }

          remainder--;

          if (active_node == root && active_length > 0) {  //rule 1

              active_length--;

              active_edge = position - remainder + 1;

          } else

              active_node = nodes[active_node].link > 0 ? nodes[active_node].link : root; //rule 3

      }

  }

}