[BAEL-3480] - Java Fast pattern matching using trie and suffix tree

macroscopic64 · macroscopic64 · commit ee114c8a173d · 2020-02-23T20:55:32.000+05:30
diff --git a/algorithms-searching/src/main/java/com/baeldung/algorithms/suffixtree/SuffixTree.java b/algorithms-searching/src/main/java/com/baeldung/algorithms/suffixtree/SuffixTree.java
@@ -14,16 +14,12 @@ public class SuffixTree {
     private Node root;
     private String fullText;
 
-    public SuffixTree() {
+    public SuffixTree(String text) {
         root = new Node("", POSITION_UNDEFINED);
-        fullText = "";
-    }
-
-    public void addText(String text) {
         for (int i = 0; i < text.length(); i++) {
             addSuffix(text.substring(i) + WORD_TERMINATION, i);
         }
-        fullText += text;
+        fullText = text;
     }
 
     public List<String> searchText(String pattern) {
@@ -151,20 +147,21 @@ private List<Node> getAllNodesInTraversePath(String pattern, Node startNode, boo
                 int compareLength = Math.min(nodeText.length(), pattern.length());
                 for (int j = 1; j < compareLength; j++) {
                     if (pattern.charAt(j) != nodeText.charAt(j)) {
-                        if (isAllowPartialMatch)
+                        if (isAllowPartialMatch) {
                             nodes.add(currentNode);
+                        }
                         return nodes;
                     }
                 }
 
                 nodes.add(currentNode);
                 if (pattern.length() > compareLength) {
                     List<Node> nodes2 = getAllNodesInTraversePath(pattern.substring(compareLength), currentNode, isAllowPartialMatch);
-                    if (nodes2.size() == 0 && !isAllowPartialMatch) {
+                    if (nodes2.size() > 0) {
+                        nodes.addAll(nodes2);
+                    } else if (!isAllowPartialMatch) {
                         nodes.add(null);
-                        return nodes;
                     }
-                    nodes.addAll(nodes2);
                 }
                 return nodes;
             }
diff --git a/algorithms-searching/src/test/java/com/baeldung/algorithms/suffixtree/SuffixTreeUnitTest.java b/algorithms-searching/src/test/java/com/baeldung/algorithms/suffixtree/SuffixTreeUnitTest.java
@@ -16,8 +16,7 @@ public class SuffixTreeUnitTest {
 
     @BeforeClass
     public static void setUp() {
-        suffixTree = new SuffixTree();
-        suffixTree.addText("bananabanana");
+        suffixTree = new SuffixTree("havanabanana");
         printTree();
     }
 
@@ -26,15 +25,15 @@ public void givenSuffixTree_whenSearchingForA_thenReturn6Matches() {
         List<String> matches = suffixTree.searchText("a");
         matches.stream()
             .forEach(m -> LOGGER.info(m));
-        Assert.assertArrayEquals(new String[] { "b[a]nanabanana", "ban[a]nabanana", "banan[a]banana", "bananab[a]nana", "bananaban[a]na", "bananabanan[a]" }, matches.toArray());
+        Assert.assertArrayEquals(new String[] { "h[a]vanabanana", "hav[a]nabanana", "havan[a]banana", "havanab[a]nana", "havanaban[a]na", "havanabanan[a]" }, matches.toArray());
     }
 
     @Test
     public void givenSuffixTree_whenSearchingForNab_thenReturn1Match() {
         List<String> matches = suffixTree.searchText("nab");
         matches.stream()
             .forEach(m -> LOGGER.info(m));
-        Assert.assertArrayEquals(new String[] { "bana[nab]anana" }, matches.toArray());
+        Assert.assertArrayEquals(new String[] { "hava[nab]anana" }, matches.toArray());
     }
 
     @Test
@@ -47,18 +46,18 @@ public void givenSuffixTree_whenSearchingForNag_thenReturnNoMatches() {
 
     @Test
     public void givenSuffixTree_whenSearchingForBanana_thenReturn2Matches() {
-        List<String> matches = suffixTree.searchText("banana");
+        List<String> matches = suffixTree.searchText("ana");
         matches.stream()
             .forEach(m -> LOGGER.info(m));
-        Assert.assertArrayEquals(new String[] { "[banana]banana", "banana[banana]" }, matches.toArray());
+        Assert.assertArrayEquals(new String[] { "hav[ana]banana", "havanab[ana]na", "havanaban[ana]" }, matches.toArray());
     }
 
     @Test
     public void givenSuffixTree_whenSearchingForNa_thenReturn4Matches() {
         List<String> matches = suffixTree.searchText("na");
         matches.stream()
             .forEach(m -> LOGGER.info(m));
-        Assert.assertArrayEquals(new String[] { "ba[na]nabanana", "bana[na]banana", "bananaba[na]na", "bananabana[na]" }, matches.toArray());
+        Assert.assertArrayEquals(new String[] { "hava[na]banana", "havanaba[na]na", "havanabana[na]" }, matches.toArray());
     }
 
     @Test
