Sphere Online Judge

SPOJ Problem Set (classical)

32. A Needle in the Haystack

Problem code: NHAY

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.


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.


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.


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

Sample output:



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
Time limit:5s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Resource:the problem was phrased and test data was supplied by Mr. Maciej 'hawk' JarzÍbski

hide comments
2014-04-15 02:16:01 Hussain
I got TLE for KMP, AC for bruteforce :\
2014-03-05 18:49:47 decoder
can someone plz help me with this code, i have implemented KMP algo. but i am getting WA
2014-02-02 06:04:29 Sachin Sai Krishna M
use string class c++ stl is really powerful
2014-01-18 05:13:55 =====e^(iπ)+1=0=====

Last edit: 2014-01-18 05:14:50
2013-12-27 08:42:18 Saimadhav Heblikar
c++ stl is really powerful!!!
2013-12-23 19:04:59 Martijn Muijsers
Yes! Awesome! Broke my record: 10 consecutive new problems AC without any 'orange'! :D

Edit: Nobody cares

Last edit: 2014-01-16 17:36:40
2013-12-13 14:28:02 arbit
I am using KMP in C. but still getting TLE. Any suggestions? I am reading the second string char by char in a while loop. and termination condition is while(eof != scanf("%c",&ch)). Anything wrong?
2013-11-06 13:09:50 harsh
chngd cin to scanf AC...!!
2013-09-05 08:51:46 Anmol Agarwal
any suggestion on not reading the haystack at once
2013-07-26 22:22:53 sobhan
i used rabin-karp algo and i got TLE :'(
now i got wrong answer :O just used scanf and printf
finally i got acc :D

Last edit: 2013-07-27 11:51:35
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.