{"id":"931318e4-95d4-4e47-b8a5-1decb6fbd277","name":"Aho Corasick - Application","description":"Given an integer n indicating the number of patterns.Then follow n lines, each containing non empty strings, representing patterns.\r\nThen comes a non empty string representing text.\r\nOutput n lines where ith line contains the positions of all occurances of the ith pattern in text.\r\n","inputFormat":"First line: n\r\nThen follow n lines, each containing non empty strings, representing patterns.\r\nNext line consists of a string, text\r\n","outputFormat":"Print n lines each consisting of occurrences of ith pattern's start index , print -1 if ith pattern doesnt occur","constraints":"|pattern| &lt; 10^5\r\n|text| &lt; 10^5","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\npublic class sol {\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 main(String[] args) {\r\n Scanner scn = new Scanner(System.in);\r\n // Write your code here\r\n\r\n }\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"6\r\nACC\r\nATC\r\nCAT\r\nGCG\r\nC\r\nT\r\nGCATCG ","sampleOutput":"-1\r\n2 \r\n1 \r\n-1\r\n1 4 \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":"93ce5bb6-2efc-4d41-8767-902719c40056","name":"Aho Corasick - Application","slug":"aho-corasick-application","type":1}],"next":{"id":"03710e95-aace-4a65-84c0-fbe30efda2c9","name":"Obscene Words Filter","type":1,"slug":"obscene-words-filter"},"prev":{"id":"afdeedab-cb15-4672-9f5d-cb136b3c98a3","name":"Suffix Tree - Dictionary Queries","type":1,"slug":"suffix-tree-dictionary-queries"}}}

Aho Corasick - Application

Given an integer n indicating the number of patterns.Then follow n lines, each containing non empty strings, representing patterns. Then comes a non empty string representing text. Output n lines where ith line contains the positions of all occurances of the ith pattern in text.

{"id":"931318e4-95d4-4e47-b8a5-1decb6fbd277","name":"Aho Corasick - Application","description":"Given an integer n indicating the number of patterns.Then follow n lines, each containing non empty strings, representing patterns.\r\nThen comes a non empty string representing text.\r\nOutput n lines where ith line contains the positions of all occurances of the ith pattern in text.\r\n","inputFormat":"First line: n\r\nThen follow n lines, each containing non empty strings, representing patterns.\r\nNext line consists of a string, text\r\n","outputFormat":"Print n lines each consisting of occurrences of ith pattern's start index , print -1 if ith pattern doesnt occur","constraints":"|pattern| &lt; 10^5\r\n|text| &lt; 10^5","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\npublic class sol {\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 main(String[] args) {\r\n Scanner scn = new Scanner(System.in);\r\n // Write your code here\r\n\r\n }\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"6\r\nACC\r\nATC\r\nCAT\r\nGCG\r\nC\r\nT\r\nGCATCG ","sampleOutput":"-1\r\n2 \r\n1 \r\n-1\r\n1 4 \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":"93ce5bb6-2efc-4d41-8767-902719c40056","name":"Aho Corasick - Application","slug":"aho-corasick-application","type":1}],"next":{"id":"03710e95-aace-4a65-84c0-fbe30efda2c9","name":"Obscene Words Filter","type":1,"slug":"obscene-words-filter"},"prev":{"id":"afdeedab-cb15-4672-9f5d-cb136b3c98a3","name":"Suffix Tree - Dictionary Queries","type":1,"slug":"suffix-tree-dictionary-queries"}}}
plane

Editor

Loading...

Aho Corasick - Application

hard

Given an integer n indicating the number of patterns.Then follow n lines, each containing non empty strings, representing patterns. Then comes a non empty string representing text. Output n lines where ith line contains the positions of all occurances of the ith pattern in text.

Constraints

|pattern| < 10^5 |text| < 10^5

Format

Input

First line: n Then follow n lines, each containing non empty strings, representing patterns. Next line consists of a string, text

Output

Print n lines each consisting of occurrences of ith pattern's start index , print -1 if ith pattern doesnt occur

Example

Sample Input

6 ACC ATC CAT GCG C T GCATCG

Sample Output

-1 2 1 -1 1 4 3

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode