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
2018-07-24 10:04:16
brute force worked in 0.02s, Weak test cases!
2018-05-18 05:25:44
I use hash table!!!
2018-01-20 16:31:06
simple bruteforce works in 0.9 sec.
2018-01-16 07:02:02
learn kmp algo from geeksforgeeks
2017-11-09 13:57:25 Rajivteja
Weak test cases.
In my first attempt after finding a match I started from the end point of the match but still got an AC.
Then I realized that my solution won't work for `aaaa aa` case.

Last edit: 2017-11-09 14:04:50
2017-08-13 15:59:59
kmp i love it
2017-07-23 13:42:42
AC using KMP!
Testcases are weak! I used a slightly wrong version of KMP, and got AC
:p

Last edit: 2017-07-23 14:44:15
2017-02-03 17:17:36
Use KMP algo!!
2017-01-27 06:28:26
AC using KMP !!
2017-01-26 14:59:57
Kmp Algorithm....
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.