Tukukkk

I solved this programming challenge where the goal is to give score to strings based on how much score certain substrings are worth (including repeating substrings).

Don't worry about what int values, valIndexes and the arguments of createTree() mean, just know that they have nothing to do with the search or organization of the data, they're only there for the score calculation.

The way this algorithm works is:

1. Creating a tree-like data structure where each node represents one prefix of a string (or the full string) from the set of substrings being searched for, with some extra links pointing from some of the nodes a to a node that represents the largest suffix of the string that a represents, to avoid backtracking.


2. Using this structure to find all the substrings with near O(N) complexity in most cases.

The performance bottleneck of my code is interlink() which creates these "extra links" in the tree, everything else works reasonably fast, any suggestions for how to fix this performance issue are greatly appreciated.

The input strings for createTree() and scan() are expected to contain only lowercase a-z characters.

class Tree {

    public int values, valIndexes;

    public Tree branches = new Tree[26];

    public Tree link;



    public static Tree createTree(String strs, int worth){

        Tree mainTree = new Tree();

        Tree currentNode;



        for(int i = 0; i < strs.length; i++){

            currentNode = mainTree;

            for(int c = 0; c < strs[i].length(); c++){

                int idx = strs[i].charAt(c) - 'a';

                if(currentNode.branches[idx] == null)

                    currentNode.branches[idx] = new Tree();

                currentNode = currentNode.branches[idx];

                if(strs[i].length() == c + 1)

                    currentNode.addValue(worth[i], i);

            }

        }

        mainTree.interlink(mainTree, "");



        return mainTree;

    }



    public int scan(String str, int minIdx, int maxIdx){

        int score = 0;

        ArrayList<Tree> nodes = new ArrayList<Tree>();

        for(int index = 0; index < str.length(); index++){



            for(int e = 0; e < nodes.size(); e++) // advance nodes to next char

                nodes.set(e, nodes.get(e).branches[str.charAt(index) - 'a']);



            while(nodes.remove(null));

            if(nodes.isEmpty()){ // if no nodes left, continue the search from first node

                nodes.add(this.branches[str.charAt(index) - 'a']);

                nodes.remove(null);

            }

            for(int e = 0; e < nodes.size(); e++){

                Tree node = nodes.get(e);

                if(node.link != null)

                    if(!nodes.contains(node.link))

                        nodes.add(node.link);



                if(node.values != null)

                    for(int x = 0; x < node.values.length; x++)

                        if(node.valIndexes[x] >= minIdx && node.valIndexes[x] <= maxIdx)

                            score += node.values[x];

            }

        }

        return score;

    }



    private void interlink(Tree mainTree, String path){

        for(int i = 0; i < branches.length; i++){

            if(branches[i] != null)

                branches[i].interlink(mainTree, path + (char)(i + 'a'));

        }

        if(path.length() < 2) return;

        Tree node;

        for(int k = 1; k < path.length(); k++){

            node = mainTree.getNode(path.substring(k));

            if(node != null){

                link = node;

                break;

            }

        }

    }



    private Tree getNode(String str){

        Tree node = this;

        for(int c = 0; c < str.length(); c++){

            node = node.branches[str.charAt(c) - 'a'];

            if(node == null)

                break;

        }

        return node;

    }



    private void addValue(int val, int idx){

        // ... this part is irrelevant ...

    }

}