{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eLittle jay really hates to deal with string. But moondy likes it very much, and she\u0027s so mischievous that she often gives jay some dull problems related to string. And one day, moondy gave jay another problem, poor jay finally broke out and cried, \" Who can help me? I\u0027ll bg him! \"\u003c/p\u003e\n\n\u003cp\u003eSo what is the problem this time?\u003c/p\u003e\n\n\u003cp\u003eFirst, moondy gave jay a very long string \u003ci\u003eA\u003c/i\u003e. Then she gave him a sequence of very short substrings, and asked him to find how many times each substring appeared in string \u003ci\u003eA\u003c/i\u003e. What\u0027s more, she would denote whether or not founded appearances of this substring are allowed to overlap.\u003c/p\u003e\n\n\u003cp\u003eAt first, jay just read string \u003ci\u003eA\u003c/i\u003e from begin to end to search all appearances of each given substring. But he soon felt exhausted and couldn\u0027t go on any more, so he gave up and broke out this time.\u003c/p\u003e\n\n\u003cp\u003eI know you\u0027re a good guy and will help with jay even without bg, won\u0027t you?\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/p\u003e\n\n\u003cp\u003eInput consists of multiple cases( \u0026lt;\u003d 20 ) and terminates with end of file.\u003c/p\u003e\n\n\u003cp\u003eFor each case, the first line contains string \u003ci\u003eA\u003c/i\u003e ( length \u0026lt;\u003d 10^5 ). The second line contains an integer \u003ci\u003eN\u003c/i\u003e ( \u003ci\u003eN\u003c/i\u003e \u0026lt;\u003d 10^5 ), which denotes the number of queries. The next \u003ci\u003eN\u003c/i\u003e lines, each with an integer \u003ci\u003etype\u003c/i\u003e and a string \u003ci\u003ea\u003c/i\u003e ( length \u0026lt;\u003d 6 ), \u003ci\u003etype\u003c/i\u003e \u003d 0 denotes substring \u003ci\u003ea\u003c/i\u003e is allowed to overlap and \u003ci\u003etype\u003c/i\u003e \u003d 1 denotes not. Note that all input characters are lowercase.\u003c/p\u003e\n\n\u003cp\u003eThere is a blank line between two consecutive cases.\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/p\u003e\n\n\u003cp\u003eFor each case, output the case number first ( based on 1 , see Samples ).\u003c/p\u003e\n\n\u003cp\u003eThen for each query, output an integer in a single line denoting the maximum times you can find the substring under certain rules.\u003c/p\u003e\n\n\u003cp\u003eOutput an empty line after each case.\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eSample Input\u003c/b\u003e\u003c/p\u003e\n\n\u003cpre\u003eab\n2\n0 ab\n1 ab\n\nabababac\n2\n0 aba\n1 aba\n\nabcdefghijklmnopqrstuvwxyz\n3\n0 abc\n1 def\n1 jmn\n\u003c/pre\u003e\n\n\u003cp\u003e\u003cb\u003eSample Output\u003c/b\u003e\u003c/p\u003e\n\n\u003cpre\u003eCase 1\n1\n1\n\nCase 2\n3\n2\n\nCase 3\n1\n1\n0\n\n\u003c/pre\u003e\n\n\u003cp\u003e\u003cb\u003eHint\u003c/b\u003e\u003c/p\u003e\n\n\u003cp\u003eIn Case 2,you can find the first substring starting in position (indexed from 0) 0,2,4, since they\u0027re allowed to overlap. The second substring starts in position 0 and 4, since they\u0027re not allowed to overlap. \u003c/p\u003e\n\n\u003cp\u003eFor C++ users, kindly use \u003cb\u003escanf\u003c/b\u003e to avoid TLE for huge inputs.\u003c/p\u003e"}}]}