NAJPF - Pattern Find


Your task is so simple given a string and a pattern. You find the pattern on the given string. If found print how many time found the pattern and their index. Otherwise print ‘Not Found’

Input:          

The input   line consists of a number T (1 ≤ T ≤ 50) test cases.

For each case given two string number  A,B. the string and the pattern  1 ≤|A|, |B| ≤10^6

All character will be lower case Latin character.  And |  | is the length of string.

Output:

For each case print the number  (found pattern from the given string) next line there position And Otherwise print 'Not Found' without quota.
There will a blank line between two cases.

Sample:

Input

Output

3
ababab ab
aaaaa bbb
aafafaasf aaf

3
1 3 5

Not Found

1
1

 

 

Hints:

Here all index is 1 base.


hide comments
Abhishek: 2016-09-27 10:36:47

Curious as to what people doing it in 0.01 are using? KMP , Z or Rabin-Karp?

->Edit : I did it 0.02 using KMP

Last edit: 2016-09-27 13:24:41
adichd123: 2016-07-04 18:45:25

Same as NHAY!!

azam_9: 2016-06-22 21:24:16

A.C. in .06s..Brute force rock..

mkfeuhrer: 2016-06-18 22:16:29

my first implementation of kmp algo !! :-) AC in one go ..

flyingduchman_: 2016-06-16 18:13:06

I used [spoiler removed] algorithm

Last edit: 2016-06-16 20:12:44
bholagabbar: 2016-05-06 19:26:32

Incase you're getting a WA in rabin karp, check for the condition where subtracting a value makes your hash negative. In that case, you'll have to add the mod to make it positive

darkhire21: 2016-01-31 08:37:57

check test case
1
aaaassss ss .

[Mayank Pratap]: 2015-10-19 09:17:07

After 3 WAs I solved this using Rabin-karp :)

[Mayank Pratap]: 2015-10-15 10:22:13

Weak test cases ..
For eg:- test cases like this can be included :-
barfoobarfoobarfoobarfoobarfoo foobarfoo

Oasis: 2015-08-04 18:55:07

i dont understand y my brute force solution is better than kmp......
kmp taking 0.48s and brute force 0.46 s

Last edit: 2015-08-04 18:56:02

Added by:Najmuzzaman
Date:2014-10-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU