{"id":"1e3ec704-ff2d-4ead-901c-4b9e56318a70","name":"Sufix Tree - Application 1 - Pattern Find","description":"Given a string S and a pattern P, print all occurrences of P in S. Use Suffix Tree only.","inputFormat":"Input consists of 2 lines\r\nFirst contains string S, second contains pattern P","outputFormat":"Print all the occurances of pattern in string","constraints":"|S| <= 10^5","sampleCode":{"cpp":{"code":""},"java":{"code":"\r\nimport 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 String pat = scn.next();\r\n\r\n // start code here\r\n }\r\n}\r\nclass SuffixTree {\r\n ///////////////////////////////////////////////////////////////// Code starts here\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":"abcbcc\r\nbc","sampleOutput":"1\r\n3\r\n","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":"776b0e41-fa81-476c-b1ac-6d9c8e074ea9","name":"Sufix Tree - Application 1 - Pattern Find","slug":"sufix-tree-application-1-pattern-find","type":1}],"next":{"id":"0bf179b9-1f1e-4efa-9262-853422493b91","name":"Suffix Tree - Application 2 - Longest Repeated Substrings","type":1,"slug":"suffix-tree-application-2-longest-repeated-substrings"},"prev":{"id":"e118eb71-66fc-42fd-82b9-fabacf6a2a86","name":"Dfs In Suffix Tree","type":1,"slug":"dfs-in-suffix-tree"}}}Given a string S and a pattern P, print all occurrences of P in S. Use Suffix Tree only.
{"id":"1e3ec704-ff2d-4ead-901c-4b9e56318a70","name":"Sufix Tree - Application 1 - Pattern Find","description":"Given a string S and a pattern P, print all occurrences of P in S. Use Suffix Tree only.","inputFormat":"Input consists of 2 lines\r\nFirst contains string S, second contains pattern P","outputFormat":"Print all the occurances of pattern in string","constraints":"|S| <= 10^5","sampleCode":{"cpp":{"code":""},"java":{"code":"\r\nimport 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 String pat = scn.next();\r\n\r\n // start code here\r\n }\r\n}\r\nclass SuffixTree {\r\n ///////////////////////////////////////////////////////////////// Code starts here\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":"abcbcc\r\nbc","sampleOutput":"1\r\n3\r\n","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":"776b0e41-fa81-476c-b1ac-6d9c8e074ea9","name":"Sufix Tree - Application 1 - Pattern Find","slug":"sufix-tree-application-1-pattern-find","type":1}],"next":{"id":"0bf179b9-1f1e-4efa-9262-853422493b91","name":"Suffix Tree - Application 2 - Longest Repeated Substrings","type":1,"slug":"suffix-tree-application-2-longest-repeated-substrings"},"prev":{"id":"e118eb71-66fc-42fd-82b9-fabacf6a2a86","name":"Dfs In Suffix Tree","type":1,"slug":"dfs-in-suffix-tree"}}}
Editor
Discussions
Show Discussion
Related Resources
