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.


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

hide comments
2016-01-31 08:37:57
check test case
1
aaaassss ss .
2015-10-19 09:17:07 [Mayank Pratap]
After 3 WAs I solved this using Rabin-karp :)
2015-10-15 10:22:13 [Mayank Pratap]
Weak test cases ..
For eg:- test cases like this can be included :-
barfoobarfoobarfoobarfoobarfoo foobarfoo
2015-08-04 18:55:07 Oasis
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
2015-07-21 15:49:05 Deepanshu Thakur
Got accepted with KMP and Z-algorithm but not sure why my Robin-Karp is giving me WA. Can anyone help me? {code link ;}

Got accepted with rabin-karp too :D

Last edit: 2015-07-23 16:50:58
2015-06-18 10:12:05 [Mayank Pratap]
C++ amazes me... :)
2015-06-01 07:48:32 ---@@@----
Easy...!!!
got 1 WA for "NOT FOUND" :p
2015-05-04 20:56:29 Shubham Sinha
I was getting wa in code block and runtime error in ideone.
But still got ac on spoj.'
Wierd!!!!
2015-02-19 12:55:32 TLE
simple rabin karp....ac :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.