ST.java

import java.io.*;
import java.util.*;

public class ST {

    class SuffixTree {
        final String ALPHABET = "abcdefghijklmnopqrstuvwxyz";
        final int oo = Integer.MAX_VALUE/2;
        Node [] nodes;
        int length = -1, currentNode = -1, needSuffixLink = -1, remainder = 0;
        final int root = 1;
        int active_node = root, active_length = 0;
        int active_edge = 0;
        char [] text;

        class Node {
            int start = -1, end = oo, parentDepth, link = -1;
            TreeMap<Character, Integer> next;
            public Node() {
                next = new TreeMap<Character, Integer>();
            }

            public Node(int start) {
                this();
                this.start = start;
            }

            public Node(int start, int end) {
                this();
                this.start = start;
                this.end = end;
            }

            public int edgeLength() {
                return Math.min(end, length + 1) - start;
            }
        }

        public SuffixTree(int length) {
            nodes = new Node[2*length + 2];
            text = new char[length];
            nodes[++currentNode] = new Node();
            nodes[++currentNode] = new Node();
            for (int i = 0; i < ALPHABET.length(); i++)
                nodes[0].next.put(ALPHABET.charAt(i), 1);
            nodes[1].link = 0;
        }



        private void addSuffixLink(int node) {
            if (needSuffixLink > 0)
                nodes[needSuffixLink].link = node;
            needSuffixLink = node;
        }

        char active_edge() {
            return active_edge < 0 ? '\0' : text[active_edge];
        }

        int step = 1;

        public void addChar(char c) throws Exception {

            needSuffixLink = -1;
            text[++length] = c;
            remainder++;
            cut:while(remainder > 0) {
                if (active_length == 0) active_edge = length;


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

                    if (active_length >= nodes[next].edgeLength()) { //if the edge we came to is shorter than active_length - go down
                        active_edge += nodes[next].edgeLength();
                        active_length -= nodes[next].edgeLength();
                        active_node = next;
                        continue cut;
                    }


                    if (text[nodes[next].start + active_length] == c) {  //character c is on the edge
                        active_length++;
                        if (active_length == nodes[next].edgeLength()) {
                            active_node = next;
                            active_edge = -1;
                            active_length = 0;
                        }
                        break;
                    }
                }
                if (!nodes[active_node].next.containsKey(active_edge())) {   //adding new node right to the active_node
                    nodes[++currentNode] = new Node(length);
                    nodes[active_node].next.put(active_edge(), currentNode);
                    remainder--;
                } else {
                    int next = nodes[active_node].next.get(active_edge());   //here we must split the edge

                    if (active_length >= nodes[next].edgeLength()) {
                        active_edge += nodes[next].edgeLength();
                        active_length -= nodes[next].edgeLength();
                        active_node = next;
                        continue cut;
                    }

                    nodes[++currentNode] = new Node(nodes[next].start, nodes[next].start + active_length); //split Node
                    nodes[active_node].next.put(active_edge(), currentNode);
                    nodes[++currentNode] = new Node(length); //node with single character on edge
                    nodes[currentNode - 1].next.put(c, currentNode);
                    nodes[next].start += active_length;
                    nodes[currentNode - 1].next.put(text[nodes[next].start], next);
                    addSuffixLink(currentNode - 1);
                    remainder--;
                }

                if (active_node == root && active_length > 0) { //after insertion, if we're at the root - set active_edge to next_suffix_to_add[0]
                    active_length--;
                    active_edge = length - remainder + 1;
                } else {
                    active_node = nodes[active_node].link > 0 ? nodes[active_node].link : root; //otherwise - follow the suffix link (or go to root)
                }
            }
        }

        int countDistinctSubstrings(int x) {
            int res = 0;
            if (x != root)
                res += nodes[x].edgeLength();
            for (int node : nodes[x].next.values())
                res += countDistinctSubstrings(node);
            return res;
        }
    }


    public ST() throws Exception {
        BufferedReader in1, in2;
        SuffixTree st = new SuffixTree(8);
        String line = "aabaaabb";
        for (int i = 0; i < line.length(); i++)
            st.addChar(line.charAt(i));

        System.out.println(st.countDistinctSubstrings(st.root));
    }

    public static void main(String ... args) throws Exception{
        new ST();
    }
}