sclass SuffixTree {

  Node root;

  S fullText;

  sclass Node {

    Substring text;

    Map<Int, Node> children; // key is first character or -1 for end of string

    IntBuffer positions;

    *() {}

    *(Substring *text) {}

    void addPosition(int i) {

      if (positions == null) positions = new IntBuffer;

      positions.add(i);

    }

    void addChild(Node n) {

      if (children == null) children = new Map;

      children.put(charToIntOrMinus1(n.text), n);

    }

    Node getChild(int c) {

      ret mapGet(children, c);

    }

  }

  *() {}

  *(S *fullText) {

    root = new Node(Substring(fullText, 0, 0));

    for i over fullText:

      addSuffix(Substring(fullText, i), i);

  }

  void addSuffix(Substring s, int position) {

    Node node = root;

    while (!empty(s)) {

      int _n = lCommonPrefix_CharSequence(node.text, s);

      s = s.substring(_n);

      if (_n >= l(node.text)) { // node text exhausted

        if (empty(s)) {

          node.addPosition(position);

          ret;

        } else {

          Node n = node.getChild(charToIntOrMinus1(s));

          if (n == null) {

            n = new Node(s);

            n.addPosition(position);

            node.addChild(n);

            ret;

          } else

            node = n;

        }

      } else { // node text not exhausted

        // split node. first, move all the node's vitals to a new node nOld

        Node nOld = new Node(node.text.substring(_n));

        nOld.positions = node.positions;

        node.positions = null;

        nOld.children = node.children;

        node.children = null;

        node.text = node.text.substring(0, _n);

        node.addChild(nOld);

        // now add a new node

        Node nNew = new Node(s);

        nNew.addPosition(position);

        node.addChild(nNew);

        ret;

      }

    }

  }

  public L<Int> indicesOf(S pattern) {

    new IntBuffer out;

    getIndicesOf(out, root, pattern, 0);

    ret out.asVirtualList();

  }

  void getIndicesOf(IntBuffer out, Node node, S pattern, int iPattern) {

    int lPattern = l(pattern);

    while true {

      int n = lCommonPrefix_CharSequence(node.text, Substring(pattern, iPattern));

      iPattern += n;

      if (iPattern >= lPattern) break;

      if (n < l(node.text)) break;

      Node child = node.getChild(charAtAsIntOrMinus1(pattern, iPattern));

      if (child != null) node = child;

    }

    collectPositions(out, node);

  }

  L<Int> getPositions(Node node) {

    new IntBuffer out;

    collectPositions(out, node);

    ret out.asVirtualList();

  }

  void collectPositions(IntBuffer out, Node node) {

    if (node == null) ret;

    out.addAll(node.positions);

    fOr (Node n : values(node.children))

      collectPositions(out, n);

  }

  void printMe() {

    printNode("", "", root);

  }

  void printNode(S indent, S pre, Node node) {

    print(indent + pre + quote(shorten(20, node.text)) + (empty(node.positions) ? "" : " " + node.positions));

    fOr (int c, Node n : node.children)

      printNode(indent + "  ", "[" + (c < 0 ? "end" : quote((char) c)) + "] ", n);

  }

}