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-05-09 13:49:20
using kmp O(n+m) 0.38 sec
2020-05-01 14:30:01
rabin karp AC one go :)
2020-04-14 21:11:43
can be done by brute force with a time complexity of O(n)


Last edit: 2020-04-14 21:13:25
2020-04-05 23:48:27
AC with Polynomial Hashing: 0.24s
2019-12-02 18:02:13
with Z algo in 0.19 secs
2019-11-14 18:27:48
Guys beware of giving the space between numbers.it cost me many WA -___-
2019-10-31 08:09:37
ac with kmp in .16 s
2019-10-15 03:02:07
If you are doing rabin-karp, and getting TLE, make sure you take care of the case when hash becomes -ve. Simply add mod to it.
2019-09-08 14:32:08
test case is rather weak, submiited a wrong solution and got accepted
test case :
aabaaabaaac aabaaac
2019-08-21 21:43:00
ac from first hit using z algorithm
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.