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
dream_kid: 2017-08-13 15:59:59

kmp i love it

arikpamnani: 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
aditya930: 2017-02-03 17:17:36

Use KMP algo!!

divya_28: 2017-01-27 06:28:26

AC using KMP !!

vengatesh15: 2017-01-26 14:59:57

Kmp Algorithm....

anurag_lal1: 2017-01-11 18:07:59

Done using KMP algo... :)

kushalanand: 2016-10-30 15:38:38

Tushar Roy's KMP lecture , probably the best tutorial. AC in one go. 1st KMP. Happy diwali :D

akt_1998: 2016-10-18 19:25:28

@chatterjee pro _/\_
I wouldn't have done this without you .._/\_

Last edit: 2016-10-18 19:47:11
sas1905: 2016-10-18 18:33:23

just follow the tag..:)

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

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