{"id":"af392436-dd7a-45a6-8783-b8a1ddc448d5","name":"Suffix Tree - Dictionary Queries","description":"You are given a string S, and Q queries.\r\nEach query consist of a string T.\r\nYou have to determine if T is a substring of S.","inputFormat":"Input consist of A string S and an integer Q followed by Q strings ","outputFormat":"If T is a substring of S, print \"y\", else print \"n\"","constraints":"|S| <= 10^5\r\nQ <= 1000\r\n|T| <= 1000","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 // Write your code here\r\n\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":"2\r\nabcdefghABCDEFGH\r\n2\r\nabc\r\nabAB\r\nxyz\r\n1\r\nxyz","sampleOutput":"y\r\nn\r\ny\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":"afdeedab-cb15-4672-9f5d-cb136b3c98a3","name":"Suffix Tree - Dictionary Queries","slug":"suffix-tree-dictionary-queries","type":1}],"next":{"id":"93ce5bb6-2efc-4d41-8767-902719c40056","name":"Aho Corasick - Application","type":1,"slug":"aho-corasick-application"},"prev":{"id":"c8b21481-7171-48c6-8c83-5348beeb5ee1","name":"Suffix Tree - Application 3 - Longest Common Substring","type":1,"slug":"suffix-tree-application-3-longest-common-substring"}}}You are given a string S, and Q queries. Each query consist of a string T. You have to determine if T is a substring of S.
{"id":"af392436-dd7a-45a6-8783-b8a1ddc448d5","name":"Suffix Tree - Dictionary Queries","description":"You are given a string S, and Q queries.\r\nEach query consist of a string T.\r\nYou have to determine if T is a substring of S.","inputFormat":"Input consist of A string S and an integer Q followed by Q strings ","outputFormat":"If T is a substring of S, print \"y\", else print \"n\"","constraints":"|S| <= 10^5\r\nQ <= 1000\r\n|T| <= 1000","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 // Write your code here\r\n\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":"2\r\nabcdefghABCDEFGH\r\n2\r\nabc\r\nabAB\r\nxyz\r\n1\r\nxyz","sampleOutput":"y\r\nn\r\ny\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":"afdeedab-cb15-4672-9f5d-cb136b3c98a3","name":"Suffix Tree - Dictionary Queries","slug":"suffix-tree-dictionary-queries","type":1}],"next":{"id":"93ce5bb6-2efc-4d41-8767-902719c40056","name":"Aho Corasick - Application","type":1,"slug":"aho-corasick-application"},"prev":{"id":"c8b21481-7171-48c6-8c83-5348beeb5ee1","name":"Suffix Tree - Application 3 - Longest Common Substring","type":1,"slug":"suffix-tree-application-3-longest-common-substring"}}}
Editor
Discussions
Show Discussion
Related Resources
