private Pair<Node, ArrayList<String>> update(final Node inputNode, final ArrayList<String> stringPart, final ArrayList<String> rest, final int value) {
        Node s = inputNode;
        ArrayList<String> tempstr = stringPart;
        String newChar = stringPart.get(stringPart.size() - 1);

        // line 1
        Node oldroot = root;

        // line 1b
        // substring
        ArrayList<String> tempstraux = new ArrayList<String>();
        for(int k=0; k<tempstr.size()-1; k++){ tempstraux.add(tempstr.get(k)); }
        
        Pair<Boolean, Node> ret = testAndSplit(s, tempstraux, newChar, rest, value);

        Node r = ret.getSecond();
        boolean endpoint = ret.getFirst();

        Node leaf;
        // line 2
        while (!endpoint) {
            // line 3
            Edge tempEdge = r.getEdge(newChar);
            if (null != tempEdge) {
                // such a node is already present. This is one of the main differences from Ukkonen's case:
                // the tree can contain deeper nodes at this stage because different strings were added by previous iterations.
                leaf = tempEdge.getDest();
            } else {
                // must build a new leaf
                leaf = new Node();
                leaf.addRef(value);
                Edge newedge = new Edge(rest, leaf);
                r.addEdge(newChar, newedge);
            }

            // update suffix link for newly created leaf
            if (activeLeaf != root) {
                activeLeaf.setSuffix(leaf);
            }
            activeLeaf = leaf;

            // line 4
            if (oldroot != root) {
                oldroot.setSuffix(r);
            }

            // line 5
            oldroot = r;

            // line 6
            if (null == s.getSuffix()) { // root node
                assert (root == s);
                // this is a special case to handle what is referred to as node _|_ on the paper
                // substring
                ArrayList<String> tempstraux2 = new ArrayList<String>();
            	for(int k=1; k<tempstr.size(); k++){ tempstraux2.add(tempstr.get(k)); }
                tempstr = tempstraux2;
            } else {
                Pair<Node, ArrayList<String>> canret = canonize(s.getSuffix(), safeCutLastChar(tempstr));
                s = canret.getFirst();
                // use intern to ensure that tempstr is a reference from the string pool
                // concat
                tempstraux = new ArrayList<String>();
                for(int k=0; k<canret.getSecond().size(); k++){ tempstraux.add(canret.getSecond().get(k)); }
                tempstraux.add(tempstr.get(tempstr.size() - 1));
                tempstr = tempstraux; 
            }

            // line 7
            ret = testAndSplit(s, safeCutLastChar(tempstr), newChar, rest, value);
            r = ret.getSecond();
            endpoint = ret.getFirst();

        }

        // line 8
        if (oldroot != root) {
            oldroot.setSuffix(r);
        }
        oldroot = root;

        return new Pair<Node, ArrayList<String>>(s, tempstr);
    }