{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp align\u003d\"justify\"\u003e\r\nWrite a program that finds all occurences of a given pattern in a given input string. This is often referred to as finding a \u003cem\u003eneedle\u003c/em\u003e in a \u003cem\u003ehaystack\u003c/em\u003e.\u003c/p\u003e\r\n\u003cp\u003eThe program has to detect \u003cstrong\u003eall\u003c/strong\u003e occurences of the needle in the haystack. It should take the needle and the haystack as input, and output the positions of each occurence, as shown below.\r\nThe suggested implementation is the KMP algorithm, but this is not a requirement. However, a naive approach will probably exceed the time limit, whereas other algorithms are more complicated... The choice is yours.\u003c/p\u003e\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe input consists of a number of test cases. Each test case is composed of three lines, containing:\u003c/p\u003e\r\n\u003cdiv align\u003d\"left\"\u003e\r\n\u003cul\u003e\r\n\t\u003cli\u003ethe length of the needle,\u003c/li\u003e\r\n\t\u003cli\u003ethe needle itself,\u003c/li\u003e\r\n\t\u003cli\u003ethe haystack.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/div\u003e\r\n\u003cp\u003eThe length of the needle is only limited by the memory available to your program, so do not make any assumptions - instead, read the length and allocate memory as needed. The haystack is \u003cstrong\u003enot\u003c/strong\u003e limited in size, which implies that your program should not read the whole haystack at once. The KMP algorithm is stream-based, i.e. it processes the haystack character by character, so this is not a problem.\u003c/p\u003e\r\n\u003cp\u003eThe test cases come one after another, each occupying three lines, with no additional space or line breaks in between.\u003c/p\u003e\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each test case your program should output all positions of the needle\u0027s occurences within the haystack. If a match is found, the output should contain the position of the first character of the match. Characters in the haystack are numbered starting with zero.\u003c/p\u003e\r\n\u003cp\u003eFor a given test case, the positions output should be sorted in ascending order, and each of these should be printed in a separate line. For two different test cases, the positions should be separated by an empty line.\u003c/p\u003e\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cpre\u003e\u003cb\u003eSample input:\u003c/b\u003e\r\n2\r\nna\r\nbanananobano\r\n6\r\nfoobar\r\nfoo\r\n9\r\nfoobarfoo\r\nbarfoobarfoobarfoobarfoobarfoo\u003c/pre\u003e\r\n\r\n\u003cpre\u003e\u003cb\u003eSample output:\u003c/b\u003e\r\n2\r\n4\r\n\r\n3\r\n9\r\n15\r\n21\r\n\u003c/pre\u003e\r\n\u003cp\u003eNote the double empty line in the output, which means that no match was found for the second test case.\u003c/p\u003e\r\n\u003cb\u003eWarning: large Input/Output data, be careful with certain languages\u003c/b\u003e\n\u003c/div\u003e"}}]}