Nsryjdtyk

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 performance bottleneck of my code is interlink(), 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){

        System.out.println("DNA sequence length = " + str.length());

        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 ...

    }

}