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

hide comments
suvro_coder: 2017-06-14 21:23:13

Tried using Z algorithm perfectly, not working, stupid problem. -_-

leafbebop: 2017-06-04 17:29:45

Note:
1. The "double empty line" is simple. If no match, no output for position, but still a empty line to separate cases. And with the empty line of the previous cases (if there is one), it becomes a double. The example output is WRONG. Though I don't know if the OJ consider it write by omitting spaces somehow.
2. Overlapping matches NEED to be print out, as the output show. I have no idea why people saying against that. Maybe test cases fixed?

and_roid: 2017-05-31 13:07:43

Is there anyone who got AC using cin, cout??
I got tle using cin,cout and AC using scanf,printf even though I am using ios_base::sync_with_stdio(false);
Same is the case in both KMP and Z algo.

akash619j: 2017-05-30 08:12:51

Got an AC with a simpler version of rabin karp,just with sum of characters as hash function!!Yay!

Last edit: 2017-05-30 08:13:10
vijayrit: 2017-05-11 12:43:07

AC in one go!! Very easy..do not get washed away by the problem description
Think for a while and you will get the solution

rishi_devan: 2017-05-07 09:26:59

You can read the entire haystack at once, doesn't seem to affect execution.

weathervane: 2017-04-22 12:25:11

What "double empty line in the output"? I can a see only a single empty line (even in the page's HTML source code). Am not going to waste my time fumbling with a poorly specified question. There are plenty of better ones.

anurag_tangri: 2017-04-10 12:41:51

AC IN ONE GO ! direct implementation

nilabja16180: 2017-02-26 13:56:19

Silly mistake costed me 5 WA! :(

cake_is_a_lie: 2017-02-14 00:46:00

1) I don't get the comments about the test cases; example 3 shows that overlapping occurrences should be detected and my solution that does detect overlapping occurrences got AC. Maybe the tests were fixed?

2) Problem wants to be something it's not - you can read the whole haystack into memory (you'd get TLE before going over 1.5GB of input anyway) and you can solve it with std::string::find unless you WANT to implement your own thing.


Added by:mima
Date:2004-06-03
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All