{"id":"26db4dea-e052-4da4-8d1f-b29bd08c9288","name":"Substring Problem","description":"https://www.spoj.com/problems/SUB_PROB/","inputFormat":"Check Link","outputFormat":"Check Link","constraints":"Check Link","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.util.*;\r\n\r\n// import jdk.internal.org.jline.terminal.impl.CursorSupport;\r\n// import jdk.internal.org.jline.utils.Curses;\r\n\r\nclass jsol {\r\n\r\n static class node {\r\n HashMap<Character, node> child = new HashMap<>();\r\n node suffix_link;\r\n node output_link;\r\n int pattern_ind;\r\n\r\n node() {\r\n this.suffix_link = null;\r\n this.output_link = null;\r\n this.pattern_ind = -1;\r\n }\r\n }\r\n\r\n public static void build_trie(node root, String[] patterns) {\r\n for (int i = 0; i < patterns.length; i++) {\r\n node curr = root;\r\n for (int j = 0; j < patterns[i].length(); j++) {\r\n char c = patterns[i].charAt(j);\r\n if (curr.child.containsKey(c)) curr = curr.child.get(c);\r\n else {\r\n node nn = new node();\r\n curr.child.put(c, nn);\r\n curr = nn;\r\n }\r\n }\r\n curr.pattern_ind = i;\r\n }\r\n }\r\n\r\n public static void build_suffix_and_output_links(node root) { // will use bfs to set links\r\n root.suffix_link = root; //root represents empty string\r\n Queue<node> qu = new LinkedList<>();\r\n\r\n for (char rc : root.child.keySet()) {\r\n qu.add(root.child.get(rc));\r\n root.child.get(rc).suffix_link = root; // root''s children suffixlink will point to root only\r\n }\r\n\r\n while (qu.size() > 0) {\r\n node curState = qu.peek();\r\n qu.remove();\r\n\r\n for (char cc : curState.child.keySet()) {\r\n node cchild = curState.child.get(cc); // jiske liye suffix link dhund rhe hein\r\n node tmp = curState.suffix_link; // parent suffix link\r\n while (!tmp.child.containsKey(cc) && tmp != root) tmp = tmp.suffix_link; //finding lps\r\n\r\n if (tmp.child.containsKey(cc)) cchild.suffix_link = tmp.child.get(cc);\r\n else cchild.suffix_link = root;\r\n qu.add(cchild);\r\n }\r\n\r\n // setting output link\r\n if (curState.suffix_link.pattern_ind >= 0) curState.output_link = curState.suffix_link;\r\n else curState.output_link = curState.suffix_link.output_link;\r\n }\r\n }\r\n\r\n public static void search(node root, String text, ArrayList<ArrayList<Integer>> searchResults) {\r\n node parent = root;\r\n\r\n for (int i = 0; i < text.length(); i++) {\r\n char c = text.charAt(i);\r\n if (parent.child.containsKey(c)) { // if parent has a child node in trie, travel it\r\n parent = parent.child.get(c);\r\n if (parent.pattern_ind >= 0) {\r\n searchResults.get(parent.pattern_ind).add(i); // reached a output node\r\n }\r\n\r\n node myOutput = parent.output_link;\r\n while (myOutput != null) {\r\n searchResults.get(myOutput.pattern_ind).add(i);\r\n myOutput = myOutput.output_link;\r\n }\r\n } else {\r\n while (parent != root && !parent.child.containsKey(c)) parent = parent.suffix_link;\r\n if (parent.child.containsKey(c)) i--; // hold i and start traversing in next iteration\r\n }\r\n }\r\n }\r\n\r\n public static void main(String[] args) {\r\n Scanner scn = new Scanner(System.in);\r\n\r\n\r\n scn.close();\r\n }\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"abghABCDE\r\n2\r\nabAB\r\nab","sampleOutput":"N\r\nY","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":"bd76237c-8ece-40fc-a883-9251a9bd16bb","name":"Substring Problem","slug":"substring-problem","type":1}],"next":null,"prev":{"id":"9df01a3c-8983-4aa5-a8ed-2dd50f076ad1","name":"String Reversal","type":1,"slug":"string-reversal"}}}

Substring Problem

https://www.spoj.com/problems/SUB_PROB/

{"id":"26db4dea-e052-4da4-8d1f-b29bd08c9288","name":"Substring Problem","description":"https://www.spoj.com/problems/SUB_PROB/","inputFormat":"Check Link","outputFormat":"Check Link","constraints":"Check Link","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.util.*;\r\n\r\n// import jdk.internal.org.jline.terminal.impl.CursorSupport;\r\n// import jdk.internal.org.jline.utils.Curses;\r\n\r\nclass jsol {\r\n\r\n static class node {\r\n HashMap<Character, node> child = new HashMap<>();\r\n node suffix_link;\r\n node output_link;\r\n int pattern_ind;\r\n\r\n node() {\r\n this.suffix_link = null;\r\n this.output_link = null;\r\n this.pattern_ind = -1;\r\n }\r\n }\r\n\r\n public static void build_trie(node root, String[] patterns) {\r\n for (int i = 0; i < patterns.length; i++) {\r\n node curr = root;\r\n for (int j = 0; j < patterns[i].length(); j++) {\r\n char c = patterns[i].charAt(j);\r\n if (curr.child.containsKey(c)) curr = curr.child.get(c);\r\n else {\r\n node nn = new node();\r\n curr.child.put(c, nn);\r\n curr = nn;\r\n }\r\n }\r\n curr.pattern_ind = i;\r\n }\r\n }\r\n\r\n public static void build_suffix_and_output_links(node root) { // will use bfs to set links\r\n root.suffix_link = root; //root represents empty string\r\n Queue<node> qu = new LinkedList<>();\r\n\r\n for (char rc : root.child.keySet()) {\r\n qu.add(root.child.get(rc));\r\n root.child.get(rc).suffix_link = root; // root''s children suffixlink will point to root only\r\n }\r\n\r\n while (qu.size() > 0) {\r\n node curState = qu.peek();\r\n qu.remove();\r\n\r\n for (char cc : curState.child.keySet()) {\r\n node cchild = curState.child.get(cc); // jiske liye suffix link dhund rhe hein\r\n node tmp = curState.suffix_link; // parent suffix link\r\n while (!tmp.child.containsKey(cc) && tmp != root) tmp = tmp.suffix_link; //finding lps\r\n\r\n if (tmp.child.containsKey(cc)) cchild.suffix_link = tmp.child.get(cc);\r\n else cchild.suffix_link = root;\r\n qu.add(cchild);\r\n }\r\n\r\n // setting output link\r\n if (curState.suffix_link.pattern_ind >= 0) curState.output_link = curState.suffix_link;\r\n else curState.output_link = curState.suffix_link.output_link;\r\n }\r\n }\r\n\r\n public static void search(node root, String text, ArrayList<ArrayList<Integer>> searchResults) {\r\n node parent = root;\r\n\r\n for (int i = 0; i < text.length(); i++) {\r\n char c = text.charAt(i);\r\n if (parent.child.containsKey(c)) { // if parent has a child node in trie, travel it\r\n parent = parent.child.get(c);\r\n if (parent.pattern_ind >= 0) {\r\n searchResults.get(parent.pattern_ind).add(i); // reached a output node\r\n }\r\n\r\n node myOutput = parent.output_link;\r\n while (myOutput != null) {\r\n searchResults.get(myOutput.pattern_ind).add(i);\r\n myOutput = myOutput.output_link;\r\n }\r\n } else {\r\n while (parent != root && !parent.child.containsKey(c)) parent = parent.suffix_link;\r\n if (parent.child.containsKey(c)) i--; // hold i and start traversing in next iteration\r\n }\r\n }\r\n }\r\n\r\n public static void main(String[] args) {\r\n Scanner scn = new Scanner(System.in);\r\n\r\n\r\n scn.close();\r\n }\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"abghABCDE\r\n2\r\nabAB\r\nab","sampleOutput":"N\r\nY","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":"bd76237c-8ece-40fc-a883-9251a9bd16bb","name":"Substring Problem","slug":"substring-problem","type":1}],"next":null,"prev":{"id":"9df01a3c-8983-4aa5-a8ed-2dd50f076ad1","name":"String Reversal","type":1,"slug":"string-reversal"}}}
plane

Editor


Loading...

Substring Problem

hard

https://www.spoj.com/problems/SUB_PROB/

Constraints

Check Link

Format

Input

Check Link

Output

Check Link

Example

Sample Input

abghABCDE 2 abAB ab

Sample Output

N Y

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode