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
2020-08-30 15:14:47
too weak test case.
what a shit problem to test the algorithm
2020-08-14 12:28:52
getting sigsegv using rabin karp.help
2020-07-24 09:44:58
AC in one go !!
2020-07-01 12:55:10
the tc seems too weak, brute force still pass
2020-06-30 11:30:54
AC in one go! 0.04 secs using KMP and global declaration of strings.
2020-06-28 19:14:26
AC in one go using Rabin Karp
2020-06-23 08:12:45
Learned both rabin karp and kmp :)
2020-05-30 20:06:46
weak test cases I later came to know that my code was wrong but it passed
2020-05-28 18:58:36
I'm getting TLE inspite of using the KMP algorithm (coded in Java), can't figure out why ...
2020-05-25 09:33:52
Using string find function , I get the Time complexity of 0.02 seconds.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.