NHAY - A Needle in the Haystack

no tags 

Write a program that finds all occurences of a given pattern in a given input string. This is often referred to as finding a needle in a haystack.

The program has to detect all 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. The 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.

Input

The input consists of a number of test cases. Each test case is composed of three lines, containing:

  • the length of the needle,
  • the needle itself,
  • the haystack.

The 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 not 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.

The test cases come one after another, each occupying three lines, with no additional space or line breaks in between.

Output

For each test case your program should output all positions of the needle's 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.

For 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.

Example

Sample input:
2 na banananobano 6 foobar foo 9 foobarfoo barfoobarfoobarfoobarfoobarfoo

Sample output:

2
4

3
9
15
21

Note the double empty line in the output, which means that no match was found for the second test case.

Warning: large Input/Output data, be careful with certain languages

Added by:Michał Małafiejski
Date:2004-06-03
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All
Resource:the problem was phrased and test data was supplied by Mr. Maciej 'hawk' Jarzębski

hide comments
yurkoflisk: 2015-08-28 23:09:31

AC in 0.06s using string.find and iostream :)

maverick_10: 2015-08-28 16:01:52

used none of kmp or Z algo just used str.find from stl libraries, got AC in one go . BUt need to study these algo as it took 2.81s that's quiet much of time .

richhiey_1996: 2015-08-18 15:14:59

AC with rabin karp in 0.18 :D

Amit Doshi: 2015-08-15 13:50:58

This is by far the worst worded problem I have solved.
"Note the double empty line in the output, which means that no match was found for the second test case."
What would one interpret this as? If there is no answer output double line. Well its not that. Wasted an entire day. The double line is printed even before the second test case is given and second test case does not output anything. No mention of end of line.
This is for new comers like me to not to get stuck in this problem.
Use Exception Handling to break out of the outer loop. There is infinite number of inputs unless you give a wrong input like a character(Pressing enter gives new line character) to an integer(length of needle).
The program flow is like this:
Input: 2
na
banananobano
Outp: 2
4
(Empty Line)
Input:6
foobar
foo
Input:9(Notice no output here from the last test case).
foobarfoo
barfoobarfoobarfoobarfoo

xavim: 2015-08-12 12:17:40

how many test cases ?

just_code21: 2015-07-29 21:04:18

nice for z algorithm...!

[Mayank Pratap]: 2015-07-26 16:06:03

I want to learn other methods too...

Baymax: 2015-07-26 14:07:47

STL "find()"s a way through in 0.51s

paranshu_12: 2015-07-23 21:08:20

Program does not input no of test cases initially??

xxbloodysantaxx: 2015-07-16 22:49:07

It's Calles the *Zee Algorithm* :D