{"id":"eb18eb14-45b6-4394-9f58-08d78429626b","name":"Dfs In Suffix Tree","description":"Suffix Tree is implemented for you, you just have to write the code for DFS traversal and print all the suffixes in lexicographical order","inputFormat":"Given a string S","outputFormat":"Output each suffix in lexicographical order on different lines","constraints":"|S| &lt;= 10^5","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.util.*;\r\n\r\npublic class Main{\r\n public static void main(String args[]) {\r\n Scanner scn = new Scanner(System.in);\r\n String s = scn.next();\r\n SuffixTree st = new SuffixTree(s`.toCharArray());\r\n st.build();\r\n\r\n st.dfs();\r\n\r\n scn.close();\r\n }\r\n}\r\nclass SuffixTree {\r\n ///////////////////////////////////////////////////////////////// Code starts here\r\n public void dfs() {\r\n // Write Code here\r\n\r\n }\r\n ///////////////////////////////////////////////////////////////// Code ends here\r\n public SuffixNode root;\r\n private Active active;\r\n private int remainingSuffixCount;\r\n private End end;\r\n private char input[];\r\n private static char UNIQUE_CHAR = ''$'';\r\n\r\n SuffixTree(char input[]) {\r\n this.input = new char[input.length + 1];\r\n for (int i = 0; i < input.length; i++) {\r\n this.input[i] = input[i];\r\n }\r\n this.input[input.length] = UNIQUE_CHAR;\r\n }\r\n\r\n public void build() {\r\n root = SuffixNode.createNode(1, new End(0));\r\n root.index = -1;\r\n active = new Active(root);\r\n this.end = new End(-1);\r\n //loop through string to start new phase\r\n for (int i = 0; i < input.length; i++) {\r\n startPhase(i);\r\n }\r\n\r\n if (remainingSuffixCount != 0) {\r\n System.out.print(\"Something wrong happened\");\r\n }\r\n //finally walk the tree again and set up the index.\r\n setIndexUsingDfs(root, 0, input.length);\r\n }\r\n\r\n private void startPhase(int i) {\r\n //set lastCreatedInternalNode to null before start of every phase.\r\n SuffixNode lastCreatedInternalNode = null;\r\n //global end for leaf. Does rule 1 extension as per trick 3 by incrementing end.\r\n end.end++;\r\n\r\n //these many suffixes need to be created.\r\n remainingSuffixCount++;\r\n while (remainingSuffixCount > 0) {\r\n //if active length is 0 then look for current character from root.\r\n if (active.activeLength == 0) {\r\n //if current character from root is not null then increase active length by 1\r\n //and break out of while loop. This is rule 3 extension and trick 2 (show stopper)\r\n if (selectNode(i) != null) {\r\n active.activeEdge = selectNode(i).start;\r\n active.activeLength++;\r\n break;\r\n } //create a new leaf node with current character from leaf. This is rule 2 extension.\r\n else {\r\n root.child[input[i]] = SuffixNode.createNode(i, end);\r\n remainingSuffixCount--;\r\n }\r\n } else {\r\n //if active length is not 0 means we are traversing somewhere in middle. So check if next character is same as\r\n //current character.\r\n try {\r\n char ch = nextChar(i);\r\n //if next character is same as current character then do a walk down. This is again a rule 3 extension and\r\n //trick 2 (show stopper).\r\n if (ch == input[i]) {\r\n //if lastCreatedInternalNode is not null means rule 2 extension happened before this. Point suffix link of that node\r\n //to selected node using active point.\r\n //TODO - Could be wrong here. Do we only do this if when walk down goes past a node or we do it every time.\r\n if (lastCreatedInternalNode != null) {\r\n lastCreatedInternalNode.suffixLink = selectNode();\r\n }\r\n //walk down and update active node if required as per rules of active node update for rule 3 extension.\r\n walkDown(i);\r\n break;\r\n }\r\n else {\r\n //next character is not same as current character so create a new internal node as per\r\n //rule 2 extension.\r\n SuffixNode node = selectNode();\r\n int oldStart = node.start;\r\n node.start = node.start + active.activeLength;\r\n //create new internal node\r\n SuffixNode newInternalNode = SuffixNode.createNode(oldStart, new End(oldStart + active.activeLength - 1));\r\n\r\n //create new leaf node\r\n SuffixNode newLeafNode = SuffixNode.createNode(i, this.end);\r\n\r\n //set internal nodes child as old node and new leaf node.\r\n newInternalNode.child[input[newInternalNode.start + active.activeLength]] = node;\r\n newInternalNode.child[input[i]] = newLeafNode;\r\n newInternalNode.index = -1;\r\n active.activeNode.child[input[newInternalNode.start]] = newInternalNode;\r\n\r\n //if another internal node was created in last extension of this phase then suffix link of that\r\n //node will be this node.\r\n if (lastCreatedInternalNode != null) {\r\n lastCreatedInternalNode.suffixLink = newInternalNode;\r\n }\r\n //set this guy as lastCreatedInternalNode and if new internalNode is created in next extension of this phase\r\n //then point suffix of this node to that node. Meanwhile set suffix of this node to root.\r\n lastCreatedInternalNode = newInternalNode;\r\n newInternalNode.suffixLink = root;\r\n\r\n //if active node is not root then follow suffix link\r\n if (active.activeNode != root) {\r\n active.activeNode = active.activeNode.suffixLink;\r\n }\r\n //if active node is root then increase active index by one and decrease active length by 1\r\n else {\r\n active.activeEdge = active.activeEdge + 1;\r\n active.activeLength--;\r\n }\r\n remainingSuffixCount--;\r\n }\r\n\r\n } catch (EndOfPathException e) {\r\n\r\n //this happens when we are looking for new character from end of current path edge. Here we already have internal node so\r\n //we don''t have to create new internal node. Just create a leaf node from here and move to suffix new link.\r\n SuffixNode node = selectNode();\r\n node.child[input[i]] = SuffixNode.createNode(i, end);\r\n if (lastCreatedInternalNode != null) {\r\n lastCreatedInternalNode.suffixLink = node;\r\n }\r\n lastCreatedInternalNode = node;\r\n //if active node is not root then follow suffix link\r\n if (active.activeNode != root) {\r\n active.activeNode = active.activeNode.suffixLink;\r\n }\r\n //if active node is root then increase active index by one and decrease active length by 1\r\n else {\r\n active.activeEdge = active.activeEdge + 1;\r\n active.activeLength--;\r\n }\r\n remainingSuffixCount--;\r\n }\r\n }\r\n }\r\n }\r\n\r\n private void walkDown(int index) {\r\n SuffixNode node = selectNode();\r\n //active length is greater than path edge length.\r\n //walk past current node so change active point.\r\n //This is as per rules of walk down for rule 3 extension.\r\n if (diff(node) < active.activeLength) {\r\n active.activeNode = node;\r\n active.activeLength = active.activeLength - diff(node);\r\n active.activeEdge = node.child[input[index]].start;\r\n } else {\r\n active.activeLength++;\r\n }\r\n }\r\n\r\n //find next character to be compared to current phase character.\r\n private char nextChar(int i) throws EndOfPathException{\r\n SuffixNode node = selectNode();\r\n if (diff(node) >= active.activeLength) {\r\n return input[active.activeNode.child[input[active.activeEdge]].start + active.activeLength];\r\n }\r\n if (diff(node) + 1 == active.activeLength ) {\r\n if (node.child[input[i]] != null) {\r\n return input[i];\r\n }\r\n }\r\n else {\r\n active.activeNode = node;\r\n active.activeLength = active.activeLength - diff(node) - 1;\r\n active.activeEdge = active.activeEdge + diff(node) + 1;\r\n return nextChar(i);\r\n }\r\n\r\n throw new EndOfPathException();\r\n }\r\n\r\n private static class EndOfPathException extends Exception {\r\n\r\n }\r\n\r\n private SuffixNode selectNode() {\r\n return active.activeNode.child[input[active.activeEdge]];\r\n }\r\n\r\n private SuffixNode selectNode(int index) {\r\n return active.activeNode.child[input[index]];\r\n }\r\n\r\n\r\n private int diff(SuffixNode node) {\r\n return node.end.end - node.start;\r\n }\r\n\r\n private void setIndexUsingDfs(SuffixNode root, int val, int size) {\r\n if (root == null) {\r\n return;\r\n }\r\n\r\n val += root.end.end - root.start + 1;\r\n if (root.index != -1) {\r\n root.index = size - val;\r\n return;\r\n }\r\n\r\n for (SuffixNode node : root.child) {\r\n setIndexUsingDfs(node, val, size);\r\n }\r\n }\r\n\r\n /**\r\n * Do a DFS traversal of the tree.\r\n */\r\n public void dfsTraversal() {\r\n List<Character> result = new ArrayList<>();\r\n for (SuffixNode node : root.child) {\r\n dfsTraversal(node, result);\r\n }\r\n }\r\n\r\n private void dfsTraversal(SuffixNode root, List<Character> result) {\r\n if (root == null) {\r\n return;\r\n }\r\n if (root.index != -1) {\r\n for (int i = root.start; i <= root.end.end; i++) {\r\n result.add(input[i]);\r\n }\r\n result.stream().forEach(System.out::print);\r\n System.out.println(\" \" + root.index);\r\n for (int i = root.start; i <= root.end.end; i++) {\r\n result.remove(result.size() - 1);\r\n }\r\n return;\r\n }\r\n\r\n for (int i = root.start; i <= root.end.end; i++) {\r\n result.add(input[i]);\r\n }\r\n\r\n for (SuffixNode node : root.child) {\r\n dfsTraversal(node, result);\r\n }\r\n\r\n for (int i = root.start; i <= root.end.end; i++) {\r\n result.remove(result.size() - 1);\r\n }\r\n\r\n }\r\n\r\n /**\r\n * Do validation of the tree by comparing all suffixes and their index at leaf node.\r\n */\r\n private boolean validate(SuffixNode root, char[] input, int index, int curr) {\r\n if (root == null) {\r\n System.out.println(\"Failed at \" + curr + \" for index \" + index);\r\n return false;\r\n }\r\n\r\n if (root.index != -1) {\r\n if (root.index != index) {\r\n System.out.println(\"Index not same. Failed at \" + curr + \" for index \" + index);\r\n return false;\r\n } else {\r\n return true;\r\n }\r\n }\r\n if (curr >= input.length) {\r\n System.out.println(\"Index not same. Failed at \" + curr + \" for index \" + index);\r\n return false;\r\n }\r\n\r\n SuffixNode node = root.child[input[curr]];\r\n if (node == null) {\r\n System.out.println(\"Failed at \" + curr + \" for index \" + index);\r\n return false;\r\n }\r\n int j = 0;\r\n for (int i = node.start ; i <= node.end.end; i++) {\r\n if (input[curr + j] != input[i] ) {\r\n System.out.println(\"Mismatch found \" + input[curr + j] + \" \" + input[i]);\r\n return false;\r\n }\r\n j++;\r\n }\r\n curr += node.end.end - node.start + 1;\r\n return validate(node, input, index, curr);\r\n }\r\n\r\n public boolean validate() {\r\n for (int i = 0; i < this.input.length; i++) {\r\n if (!validate(this.root, this.input, i, i)) {\r\n System.out.println(\"Failed validation\");\r\n return false;\r\n }\r\n }\r\n return true;\r\n }\r\n}\r\n\r\nclass SuffixNode {\r\n\r\n private SuffixNode() {\r\n }\r\n\r\n private static final int TOTAL = 256;\r\n SuffixNode[] child = new SuffixNode[TOTAL];\r\n\r\n int start;\r\n End end;\r\n int index;\r\n\r\n SuffixNode suffixLink;\r\n\r\n public static SuffixNode createNode(int start, End end) {\r\n SuffixNode node = new SuffixNode();\r\n node.start = start;\r\n node.end = end;\r\n return node;\r\n }\r\n\r\n @Override\r\n public String toString() {\r\n StringBuffer buffer = new StringBuffer();\r\n int i = 0;\r\n for (SuffixNode node : child) {\r\n if (node != null) {\r\n buffer.append((char)i + \" \");\r\n }\r\n i++;\r\n }\r\n return \"SuffixNode [start=\" + start + \"]\" + \" \" + buffer.toString();\r\n }\r\n}\r\n\r\nclass End {\r\n public End(int end) {\r\n this.end = end;\r\n }\r\n int end;\r\n}\r\n\r\nclass Active {\r\n Active(SuffixNode node) {\r\n activeLength = 0;\r\n activeNode = node;\r\n activeEdge = -1;\r\n }\r\n\r\n @Override\r\n public String toString() {\r\n return \"Active [activeNode=\" + activeNode + \", activeIndex=\" + activeEdge + \", activeLength=\" + activeLength + \"]\";\r\n }\r\n\r\n SuffixNode activeNode;\r\n int activeEdge;\r\n int activeLength;\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"abca","sampleOutput":"$\r\na$\r\nabca$\r\nbca$\r\nca$","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"a2073e25-96a1-4875-b400-f40bbe2edd95","name":"Text Processing For Experts","slug":"text-processing-for-experts-859","type":0},{"id":"e118eb71-66fc-42fd-82b9-fabacf6a2a86","name":"Dfs In Suffix Tree","slug":"dfs-in-suffix-tree","type":1}],"next":{"id":"776b0e41-fa81-476c-b1ac-6d9c8e074ea9","name":"Sufix Tree - Application 1 - Pattern Find","type":1,"slug":"sufix-tree-application-1-pattern-find"},"prev":{"id":"c64a5455-09e9-4d26-9e4a-8a5eb00392fa","name":"Hidden Password - Icpc Regionals","type":1,"slug":"hidden-password-icpc-regionals"}}}

Dfs In Suffix Tree

Suffix Tree is implemented for you, you just have to write the code for DFS traversal and print all the suffixes in lexicographical order

{"id":"eb18eb14-45b6-4394-9f58-08d78429626b","name":"Dfs In Suffix Tree","description":"Suffix Tree is implemented for you, you just have to write the code for DFS traversal and print all the suffixes in lexicographical order","inputFormat":"Given a string S","outputFormat":"Output each suffix in lexicographical order on different lines","constraints":"|S| &lt;= 10^5","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.util.*;\r\n\r\npublic class Main{\r\n public static void main(String args[]) {\r\n Scanner scn = new Scanner(System.in);\r\n String s = scn.next();\r\n SuffixTree st = new SuffixTree(s`.toCharArray());\r\n st.build();\r\n\r\n st.dfs();\r\n\r\n scn.close();\r\n }\r\n}\r\nclass SuffixTree {\r\n ///////////////////////////////////////////////////////////////// Code starts here\r\n public void dfs() {\r\n // Write Code here\r\n\r\n }\r\n ///////////////////////////////////////////////////////////////// Code ends here\r\n public SuffixNode root;\r\n private Active active;\r\n private int remainingSuffixCount;\r\n private End end;\r\n private char input[];\r\n private static char UNIQUE_CHAR = ''$'';\r\n\r\n SuffixTree(char input[]) {\r\n this.input = new char[input.length + 1];\r\n for (int i = 0; i < input.length; i++) {\r\n this.input[i] = input[i];\r\n }\r\n this.input[input.length] = UNIQUE_CHAR;\r\n }\r\n\r\n public void build() {\r\n root = SuffixNode.createNode(1, new End(0));\r\n root.index = -1;\r\n active = new Active(root);\r\n this.end = new End(-1);\r\n //loop through string to start new phase\r\n for (int i = 0; i < input.length; i++) {\r\n startPhase(i);\r\n }\r\n\r\n if (remainingSuffixCount != 0) {\r\n System.out.print(\"Something wrong happened\");\r\n }\r\n //finally walk the tree again and set up the index.\r\n setIndexUsingDfs(root, 0, input.length);\r\n }\r\n\r\n private void startPhase(int i) {\r\n //set lastCreatedInternalNode to null before start of every phase.\r\n SuffixNode lastCreatedInternalNode = null;\r\n //global end for leaf. Does rule 1 extension as per trick 3 by incrementing end.\r\n end.end++;\r\n\r\n //these many suffixes need to be created.\r\n remainingSuffixCount++;\r\n while (remainingSuffixCount > 0) {\r\n //if active length is 0 then look for current character from root.\r\n if (active.activeLength == 0) {\r\n //if current character from root is not null then increase active length by 1\r\n //and break out of while loop. This is rule 3 extension and trick 2 (show stopper)\r\n if (selectNode(i) != null) {\r\n active.activeEdge = selectNode(i).start;\r\n active.activeLength++;\r\n break;\r\n } //create a new leaf node with current character from leaf. This is rule 2 extension.\r\n else {\r\n root.child[input[i]] = SuffixNode.createNode(i, end);\r\n remainingSuffixCount--;\r\n }\r\n } else {\r\n //if active length is not 0 means we are traversing somewhere in middle. So check if next character is same as\r\n //current character.\r\n try {\r\n char ch = nextChar(i);\r\n //if next character is same as current character then do a walk down. This is again a rule 3 extension and\r\n //trick 2 (show stopper).\r\n if (ch == input[i]) {\r\n //if lastCreatedInternalNode is not null means rule 2 extension happened before this. Point suffix link of that node\r\n //to selected node using active point.\r\n //TODO - Could be wrong here. Do we only do this if when walk down goes past a node or we do it every time.\r\n if (lastCreatedInternalNode != null) {\r\n lastCreatedInternalNode.suffixLink = selectNode();\r\n }\r\n //walk down and update active node if required as per rules of active node update for rule 3 extension.\r\n walkDown(i);\r\n break;\r\n }\r\n else {\r\n //next character is not same as current character so create a new internal node as per\r\n //rule 2 extension.\r\n SuffixNode node = selectNode();\r\n int oldStart = node.start;\r\n node.start = node.start + active.activeLength;\r\n //create new internal node\r\n SuffixNode newInternalNode = SuffixNode.createNode(oldStart, new End(oldStart + active.activeLength - 1));\r\n\r\n //create new leaf node\r\n SuffixNode newLeafNode = SuffixNode.createNode(i, this.end);\r\n\r\n //set internal nodes child as old node and new leaf node.\r\n newInternalNode.child[input[newInternalNode.start + active.activeLength]] = node;\r\n newInternalNode.child[input[i]] = newLeafNode;\r\n newInternalNode.index = -1;\r\n active.activeNode.child[input[newInternalNode.start]] = newInternalNode;\r\n\r\n //if another internal node was created in last extension of this phase then suffix link of that\r\n //node will be this node.\r\n if (lastCreatedInternalNode != null) {\r\n lastCreatedInternalNode.suffixLink = newInternalNode;\r\n }\r\n //set this guy as lastCreatedInternalNode and if new internalNode is created in next extension of this phase\r\n //then point suffix of this node to that node. Meanwhile set suffix of this node to root.\r\n lastCreatedInternalNode = newInternalNode;\r\n newInternalNode.suffixLink = root;\r\n\r\n //if active node is not root then follow suffix link\r\n if (active.activeNode != root) {\r\n active.activeNode = active.activeNode.suffixLink;\r\n }\r\n //if active node is root then increase active index by one and decrease active length by 1\r\n else {\r\n active.activeEdge = active.activeEdge + 1;\r\n active.activeLength--;\r\n }\r\n remainingSuffixCount--;\r\n }\r\n\r\n } catch (EndOfPathException e) {\r\n\r\n //this happens when we are looking for new character from end of current path edge. Here we already have internal node so\r\n //we don''t have to create new internal node. Just create a leaf node from here and move to suffix new link.\r\n SuffixNode node = selectNode();\r\n node.child[input[i]] = SuffixNode.createNode(i, end);\r\n if (lastCreatedInternalNode != null) {\r\n lastCreatedInternalNode.suffixLink = node;\r\n }\r\n lastCreatedInternalNode = node;\r\n //if active node is not root then follow suffix link\r\n if (active.activeNode != root) {\r\n active.activeNode = active.activeNode.suffixLink;\r\n }\r\n //if active node is root then increase active index by one and decrease active length by 1\r\n else {\r\n active.activeEdge = active.activeEdge + 1;\r\n active.activeLength--;\r\n }\r\n remainingSuffixCount--;\r\n }\r\n }\r\n }\r\n }\r\n\r\n private void walkDown(int index) {\r\n SuffixNode node = selectNode();\r\n //active length is greater than path edge length.\r\n //walk past current node so change active point.\r\n //This is as per rules of walk down for rule 3 extension.\r\n if (diff(node) < active.activeLength) {\r\n active.activeNode = node;\r\n active.activeLength = active.activeLength - diff(node);\r\n active.activeEdge = node.child[input[index]].start;\r\n } else {\r\n active.activeLength++;\r\n }\r\n }\r\n\r\n //find next character to be compared to current phase character.\r\n private char nextChar(int i) throws EndOfPathException{\r\n SuffixNode node = selectNode();\r\n if (diff(node) >= active.activeLength) {\r\n return input[active.activeNode.child[input[active.activeEdge]].start + active.activeLength];\r\n }\r\n if (diff(node) + 1 == active.activeLength ) {\r\n if (node.child[input[i]] != null) {\r\n return input[i];\r\n }\r\n }\r\n else {\r\n active.activeNode = node;\r\n active.activeLength = active.activeLength - diff(node) - 1;\r\n active.activeEdge = active.activeEdge + diff(node) + 1;\r\n return nextChar(i);\r\n }\r\n\r\n throw new EndOfPathException();\r\n }\r\n\r\n private static class EndOfPathException extends Exception {\r\n\r\n }\r\n\r\n private SuffixNode selectNode() {\r\n return active.activeNode.child[input[active.activeEdge]];\r\n }\r\n\r\n private SuffixNode selectNode(int index) {\r\n return active.activeNode.child[input[index]];\r\n }\r\n\r\n\r\n private int diff(SuffixNode node) {\r\n return node.end.end - node.start;\r\n }\r\n\r\n private void setIndexUsingDfs(SuffixNode root, int val, int size) {\r\n if (root == null) {\r\n return;\r\n }\r\n\r\n val += root.end.end - root.start + 1;\r\n if (root.index != -1) {\r\n root.index = size - val;\r\n return;\r\n }\r\n\r\n for (SuffixNode node : root.child) {\r\n setIndexUsingDfs(node, val, size);\r\n }\r\n }\r\n\r\n /**\r\n * Do a DFS traversal of the tree.\r\n */\r\n public void dfsTraversal() {\r\n List<Character> result = new ArrayList<>();\r\n for (SuffixNode node : root.child) {\r\n dfsTraversal(node, result);\r\n }\r\n }\r\n\r\n private void dfsTraversal(SuffixNode root, List<Character> result) {\r\n if (root == null) {\r\n return;\r\n }\r\n if (root.index != -1) {\r\n for (int i = root.start; i <= root.end.end; i++) {\r\n result.add(input[i]);\r\n }\r\n result.stream().forEach(System.out::print);\r\n System.out.println(\" \" + root.index);\r\n for (int i = root.start; i <= root.end.end; i++) {\r\n result.remove(result.size() - 1);\r\n }\r\n return;\r\n }\r\n\r\n for (int i = root.start; i <= root.end.end; i++) {\r\n result.add(input[i]);\r\n }\r\n\r\n for (SuffixNode node : root.child) {\r\n dfsTraversal(node, result);\r\n }\r\n\r\n for (int i = root.start; i <= root.end.end; i++) {\r\n result.remove(result.size() - 1);\r\n }\r\n\r\n }\r\n\r\n /**\r\n * Do validation of the tree by comparing all suffixes and their index at leaf node.\r\n */\r\n private boolean validate(SuffixNode root, char[] input, int index, int curr) {\r\n if (root == null) {\r\n System.out.println(\"Failed at \" + curr + \" for index \" + index);\r\n return false;\r\n }\r\n\r\n if (root.index != -1) {\r\n if (root.index != index) {\r\n System.out.println(\"Index not same. Failed at \" + curr + \" for index \" + index);\r\n return false;\r\n } else {\r\n return true;\r\n }\r\n }\r\n if (curr >= input.length) {\r\n System.out.println(\"Index not same. Failed at \" + curr + \" for index \" + index);\r\n return false;\r\n }\r\n\r\n SuffixNode node = root.child[input[curr]];\r\n if (node == null) {\r\n System.out.println(\"Failed at \" + curr + \" for index \" + index);\r\n return false;\r\n }\r\n int j = 0;\r\n for (int i = node.start ; i <= node.end.end; i++) {\r\n if (input[curr + j] != input[i] ) {\r\n System.out.println(\"Mismatch found \" + input[curr + j] + \" \" + input[i]);\r\n return false;\r\n }\r\n j++;\r\n }\r\n curr += node.end.end - node.start + 1;\r\n return validate(node, input, index, curr);\r\n }\r\n\r\n public boolean validate() {\r\n for (int i = 0; i < this.input.length; i++) {\r\n if (!validate(this.root, this.input, i, i)) {\r\n System.out.println(\"Failed validation\");\r\n return false;\r\n }\r\n }\r\n return true;\r\n }\r\n}\r\n\r\nclass SuffixNode {\r\n\r\n private SuffixNode() {\r\n }\r\n\r\n private static final int TOTAL = 256;\r\n SuffixNode[] child = new SuffixNode[TOTAL];\r\n\r\n int start;\r\n End end;\r\n int index;\r\n\r\n SuffixNode suffixLink;\r\n\r\n public static SuffixNode createNode(int start, End end) {\r\n SuffixNode node = new SuffixNode();\r\n node.start = start;\r\n node.end = end;\r\n return node;\r\n }\r\n\r\n @Override\r\n public String toString() {\r\n StringBuffer buffer = new StringBuffer();\r\n int i = 0;\r\n for (SuffixNode node : child) {\r\n if (node != null) {\r\n buffer.append((char)i + \" \");\r\n }\r\n i++;\r\n }\r\n return \"SuffixNode [start=\" + start + \"]\" + \" \" + buffer.toString();\r\n }\r\n}\r\n\r\nclass End {\r\n public End(int end) {\r\n this.end = end;\r\n }\r\n int end;\r\n}\r\n\r\nclass Active {\r\n Active(SuffixNode node) {\r\n activeLength = 0;\r\n activeNode = node;\r\n activeEdge = -1;\r\n }\r\n\r\n @Override\r\n public String toString() {\r\n return \"Active [activeNode=\" + activeNode + \", activeIndex=\" + activeEdge + \", activeLength=\" + activeLength + \"]\";\r\n }\r\n\r\n SuffixNode activeNode;\r\n int activeEdge;\r\n int activeLength;\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"abca","sampleOutput":"$\r\na$\r\nabca$\r\nbca$\r\nca$","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"a2073e25-96a1-4875-b400-f40bbe2edd95","name":"Text Processing For Experts","slug":"text-processing-for-experts-859","type":0},{"id":"e118eb71-66fc-42fd-82b9-fabacf6a2a86","name":"Dfs In Suffix Tree","slug":"dfs-in-suffix-tree","type":1}],"next":{"id":"776b0e41-fa81-476c-b1ac-6d9c8e074ea9","name":"Sufix Tree - Application 1 - Pattern Find","type":1,"slug":"sufix-tree-application-1-pattern-find"},"prev":{"id":"c64a5455-09e9-4d26-9e4a-8a5eb00392fa","name":"Hidden Password - Icpc Regionals","type":1,"slug":"hidden-password-icpc-regionals"}}}
plane

Editor


Loading...

Dfs In Suffix Tree

hard

Suffix Tree is implemented for you, you just have to write the code for DFS traversal and print all the suffixes in lexicographical order

Constraints

|S| <= 10^5

Format

Input

Given a string S

Output

Output each suffix in lexicographical order on different lines

Example

Sample Input

abca

Sample Output

$ a$ abca$ bca$ ca$

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode