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

/*
 Ukkonen's algorithm for linear time construction of suffix trees.
*/

public static int stacktrack;
public char TERMINATORS_RANGE = '\ud800';
public static int count=0;
public static void dfsd(Node c){
  if (c.isLeaf()){
    //print("\nbasecase");
    //count++;
    return;
  }
  Node a;
  print(c.sons.keySet());
  
  Iterator it = c.sons.entrySet().iterator();
  while (it.hasNext()) {
    Map.Entry pairs = (Map.Entry)it.next();
    a = (Node)pairs.getValue();
    for(int i=0;i<stacktrack;i++)System.out.print("\t");
    print(stacktrack+" br>>>>>>> ="+count+"= "+pairs.getKey() + " = " + a.edgeStart + " : " + a.edgeEnd );
    stacktrack++;
    count++;
    dfsd(a);
  
    stacktrack--;
    for(int i=0;i<stacktrack;i++)System.out.print("\t");
    print(stacktrack+" bt<<<<<<< ="+count+"= "+pairs.getKey() + " = " + a.edgeStart + " : " + a.edgeEnd );
  }
}
        
p-exp {
  /*Scanner sc = new Scanner(System.in);
  int n = sc.nextInt();
  sc.nextLine();
  */
  
  S s = "abbab";
  SuffixTree t1 = new SuffixTree(print(s));
  print("Number of nodes: " + t1.nofnodes());
  t1 = new SuffixTree(printStruct(new String[]{"aab","aac"}));
  print("Number of nodes: " + t1.nofnodes());

  t1 = new SuffixTree;
  t1.addString(print("aab"));
  t1.addString(print("aac"));
  print("Number of nodes: " + t1.nofnodes());
  dfsd(t1.root);
  print(+count);
}

sclass Node {
  Node parent, suffixLink;
  int edgeStart, edgeEnd, parentDepth;
  // The edge that reaches this node contains the substring s[edgeStart, edgeEnd]
  TreeMap<Character, Node> sons;

  public Node(){
    parent = suffixLink = null;
    edgeStart = edgeEnd = parentDepth = 0;
    sons = new TreeMap<Character, Node>();
  }

  // Returns true if there is a path starting at root having length position + 1 that ends
  // in the edge that reaches this node.
  public boolean inEdge(int position){
    return parentDepth <= position && position < depth();
  }

  public int edgeLength(){
    return edgeEnd - edgeStart;
  }

  public int depth(){
    return parentDepth + edgeLength();
  }

  void link(Node son, int start, int end, String s){
    // Links the current node with the son. The edge will have substring s[start, end)
    son.parent = this;
    son.parentDepth = this.depth();
    son.edgeStart = start;
    son.edgeEnd = end;
    sons.put(s.charAt(start),son);
  }

  public boolean isLeaf(){
    return sons.size() == 0;
  }
};

sclass SuffixTree {
  ArrayList<Node> nodes;
  Node root, needSuffix;
  int currentNode;
  int length;
  char TERMINATORS_RANGE = '\ud800';
  int termi=0;
  String generalized;

  public SuffixTree(String str) {
    nodes = new ArrayList<Node>();
    currentNode = 0;
    str = str + (char)TERMINATORS_RANGE;
    length = str.length();
    root = newNode();
    build(root, str);
  }

  public SuffixTree(String[] stra) {
    nodes = new ArrayList<Node>();
    currentNode = 0;
    root = newNode();
    
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < stra.length; i++) {
        sb.append(stra[i]);
        sb.append((char)(TERMINATORS_RANGE + i));
    }
    generalized = sb.toString();
    length = generalized.length();
    build(root, generalized); 
  }

  public SuffixTree() {
    nodes = new ArrayList<Node>();
    currentNode = 0;
    root = newNode();
  }
  
  void addString(String str){
    str = str+ (char)(TERMINATORS_RANGE + termi);
    termi++;
    length = str.length();
    build(root, str);
  } 
  
  int nofnodes() {
    return currentNode;
  }
  
  Node newNode(){
    new Node node;
    nodes.add(currentNode, node);
    currentNode++;
    ret node;
  }

  Node walkDown(Node c, int j, int i, String str) {
    int k = j + c.depth();
    if (i - j + 1 > 0){
      while (!c.inEdge(i - j)){
        c = c.sons.get(str.charAt(k));
        k += c.edgeLength();
      }
    }
    return c;
  }

  void addSuffixLink(Node current){
    if (needSuffix != null){
      needSuffix.suffixLink = current;
    }
    needSuffix = null;
  }

  void build(Node root, String s) {
    
    Node c = newNode();
    needSuffix = null;
    root.link(c, 0, length, s);

    // Indicates if at the beginning of the phase we need to follow the suffix link of the current node 
    //and then walk down the tree using the skip and count trick.
    boolean needWalk = true;

    for (int i=0, j=1; i<length-1; ++i){
      char nc = s.charAt(i+1);
      while (j <= i + 1){
        if (needWalk){
          if (c.suffixLink == null && c.parent != null) c = c.parent;
          c = (c.suffixLink == null ? root : c.suffixLink);
          c = walkDown(c, j, i, s);
        }

        needWalk = true;
        // Here c == the highest node below s[j...i] and we will add char s[i+1]
        int m = i - j + 1; // Length of the string s[j..i].
        if (m == c.depth()){
          // String s[j...i] ends exactly at node c (explicit node).
          addSuffixLink(c);
          if (c.sons.containsKey(nc)){
            c = c.sons.get(nc);
            needWalk = false;
            break;
          }else{
            Node leaf = newNode();
            c.link(leaf, i+1, length, s);
          }
        }else{
          // String s[j...i] ends at some place in the edge that reaches node c.
          int where = c.edgeStart + m - c.parentDepth;
          // The next character in the path after string s[j...i] is s[where]
          if (s.charAt(where) == nc){ //Either rule 3 or rule 1
            addSuffixLink(c);
            if (!c.isLeaf() || j != c.edgeStart - c.parentDepth){
              // Rule 3
              needWalk = false;
              break;
            }
          }else{
            Node split = newNode();
            c.parent.link(split, c.edgeStart, where, s);
            split.link(c, where, c.edgeEnd, s);
            split.link(newNode(), i+1, length, s);
      
            addSuffixLink(split);
      
            if (split.depth() == 1){
              //The suffix link is the root because we remove the only character and end with an empty string.
              split.suffixLink = root;
            }else{
              needSuffix = split;
            }
            c = split;
          }
        }
        j++;
      }
    }
  }
}