sclass SuffixTree { Node root; S fullText; S textWithTerminator; // all Substrings are constructed off this private static final String WORD_TERMINATION = "$"; private static final int POSITION_UNDEFINED = -1; sclass Node { Substring text; new L children; int position; *(Substring *text, int *position) {} Substring getText() { ret text; } void setText(Substring text) { //print("Setting text: " + quote(this.text) + " => " + quote(text); this.text = text; } int getPosition() { ret position; } void setPosition(int position) { this.position = position; } L getChildren() { ret children; } void setChildren(L children) { this.children = children; } S printTree(String depthIndicator) { S str = ""; S positionStr = position > -1 ? "[" + position + "]" : ""; str += depthIndicator + text + positionStr + "\n"; for (int i = 0; i < children.size(); i++) str += children.get(i).printTree(depthIndicator + "\t"); return str; } toString { ret printTree(""); } } *(S text) { textWithTerminator = text + WORD_TERMINATION; root = new Node(Substring(textWithTerminator, 0, 0), POSITION_UNDEFINED); for i over text: addSuffix(Substring(textWithTerminator, i), i); fullText = text; } public LS markText(S pattern) { //LOGGER.info("Searching for pattern \"{}\"", pattern); new LS result; L nodes = getAllNodesInTraversePath(pattern, root, false); if (nodes.size() > 0) { Node lastNode = nodes.get(nodes.size() - 1); if (lastNode != null) { L positions = getPositions(lastNode); sortInPlace(positions); positions.forEach(m -> result.add((markPatternInText(m, pattern)))); } } return result; } private void addSuffix(Substring suffix, int position) { //print("Adding new suffix: " + quote(suffix)); List nodes = getAllNodesInTraversePath(suffix, root, true); if (nodes.size() == 0) { addChildNode(root, suffix, position); //LOGGER.info("{}", printTree()); } else { Node lastNode = nodes.remove(nodes.size() - 1); Substring newText = suffix; if (nodes.size() > 0) { Substring existingSuffixUptoLastNode = joinSubstringObjects(map(nodes, a -> a.getText())); // Remove prefix from newText already included in parent newText = newText.substring(existingSuffixUptoLastNode.length()); } extendNode(lastNode, newText, position); //LOGGER.info("{}", printTree()); } } private List getPositions(Node node) { List positions = new ArrayList<>(); if (node.getText() /*.endsWith(WORD_TERMINATION)*/.endsAtEnd()) { positions.add(node.getPosition()); } for (int i = 0; i < node.getChildren() .size(); i++) { positions.addAll(getPositions(node.getChildren() .get(i))); } return positions; } private String markPatternInText(Integer startPosition, String pattern) { String matchingTextLHS = fullText.substring(0, startPosition); String matchingText = fullText.substring(startPosition, startPosition + pattern.length()); String matchingTextRHS = fullText.substring(startPosition + pattern.length()); return matchingTextLHS + "[" + matchingText + "]" + matchingTextRHS; } private void addChildNode(Node parentNode, Substring text, int position) { parentNode.getChildren() .add(new Node(text, position)); } private void extendNode(Node node, Substring newText, int position) { Substring currentText = node.getText(); Substring commonPrefix = getLongestCommonPrefix(currentText, newText); if (neq(commonPrefix, currentText)) { Substring parentText = currentText.substring(0, commonPrefix.length()); Substring childText = currentText.substring(commonPrefix.length()); splitNodeToParentAndChild(node, parentText, childText); } Substring remainingText = newText.substring(commonPrefix.length()); addChildNode(node, remainingText, position); } private void splitNodeToParentAndChild(Node parentNode, Substring parentNewText, Substring childNewText) { Node childNode = new Node(childNewText, parentNode.getPosition()); while (parentNode.getChildren().size() > 0) childNode.getChildren().add(parentNode.getChildren().remove(0)); parentNode.getChildren().add(childNode); parentNode.setText(parentNewText); parentNode.setPosition(POSITION_UNDEFINED); } private Substring getLongestCommonPrefix(Substring str1, Substring str2) { int compareLength = Math.min(str1.length(), str2.length()); for (int i = 0; i < compareLength; i++) if (str1.charAt(i) != str2.charAt(i)) ret str1.substring(0, i); ret str1.substring(0, compareLength); } private L getAllNodesInTraversePath(CharSequence pattern, Node startNode, boolean isAllowPartialMatch) { new L nodes; for (int i = 0; i < startNode.getChildren().size(); i++) { Node currentNode = startNode.getChildren().get(i); CharSequence nodeText = currentNode.getText(); if (empty(nodeText)) fail("Node text empty: " + currentNode); if (pattern.charAt(0) == nodeText.charAt(0)) { if (isAllowPartialMatch && pattern.length() <= nodeText.length()) { nodes.add(currentNode); return nodes; } int compareLength = Math.min(nodeText.length(), pattern.length()); for (int j = 1; j < compareLength; j++) { if (pattern.charAt(j) != nodeText.charAt(j)) { if (isAllowPartialMatch) { nodes.add(currentNode); } return nodes; } } nodes.add(currentNode); if (pattern.length() > compareLength) { List nodes2 = getAllNodesInTraversePath(subCharSequence(pattern, compareLength), currentNode, isAllowPartialMatch); if (nodes2.size() > 0) { nodes.addAll(nodes2); } else if (!isAllowPartialMatch) { nodes.add(null); } } return nodes; } } return nodes; } S printTree() { ret root.printTree(""); } }