{"id":"6ae6a4f3-21c0-4ef8-a03a-23a516e21f5b","name":"Obscene Words Filter","description":"https://acm.timus.ru/problem.aspx?space=1&num=1269","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\npublic class Main {\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 scn.close();\r\n }\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"5\r\ndear\r\nsweetie\r\nangel\r\ndream\r\nbaby\r\n8\r\nHad I the heavens'' embroidered cloths, \r\nEnwrought with golden and silver light, \r\nThe blue and the dim and the dark cloths \r\nOf night and light and the half-light, \r\nI would spread the cloths under your feet: \r\nBut I, being poor, have only my dreams; \r\nI have spread my dreams under your feet; \r\nTread softly because you tread on my dreams.","sampleOutput":"6 33","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":"03710e95-aace-4a65-84c0-fbe30efda2c9","name":"Obscene Words Filter","slug":"obscene-words-filter","type":1}],"next":{"id":"85767405-7800-48bd-ac6a-717b81d3aa34","name":"Vitaly And Strings","type":1,"slug":"vitaly-and-strings"},"prev":{"id":"93ce5bb6-2efc-4d41-8767-902719c40056","name":"Aho Corasick - Application","type":1,"slug":"aho-corasick-application"}}}

Obscene Words Filter

https://acm.timus.ru/problem.aspx?space=1&num=1269

{"id":"6ae6a4f3-21c0-4ef8-a03a-23a516e21f5b","name":"Obscene Words Filter","description":"https://acm.timus.ru/problem.aspx?space=1&num=1269","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\npublic class Main {\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 scn.close();\r\n }\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"5\r\ndear\r\nsweetie\r\nangel\r\ndream\r\nbaby\r\n8\r\nHad I the heavens'' embroidered cloths, \r\nEnwrought with golden and silver light, \r\nThe blue and the dim and the dark cloths \r\nOf night and light and the half-light, \r\nI would spread the cloths under your feet: \r\nBut I, being poor, have only my dreams; \r\nI have spread my dreams under your feet; \r\nTread softly because you tread on my dreams.","sampleOutput":"6 33","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":"03710e95-aace-4a65-84c0-fbe30efda2c9","name":"Obscene Words Filter","slug":"obscene-words-filter","type":1}],"next":{"id":"85767405-7800-48bd-ac6a-717b81d3aa34","name":"Vitaly And Strings","type":1,"slug":"vitaly-and-strings"},"prev":{"id":"93ce5bb6-2efc-4d41-8767-902719c40056","name":"Aho Corasick - Application","type":1,"slug":"aho-corasick-application"}}}
plane

Editor

Loading...

Obscene Words Filter

hard

https://acm.timus.ru/problem.aspx?space=1&num=1269

Constraints

Check Link

Format

Input

Check Link

Output

Check Link

Example

Sample Input

5 dear sweetie angel dream baby 8 Had I the heavens'' embroidered cloths, Enwrought with golden and silver light, The blue and the dim and the dark cloths Of night and light and the half-light, I would spread the cloths under your feet: But I, being poor, have only my dreams; I have spread my dreams under your feet; Tread softly because you tread on my dreams.

Sample Output

6 33

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode