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
copperium: 2019-08-12 05:39:32

"Not Found" has both words capitalized, cost me 2 WA

sagar_june97p: 2019-08-08 16:36:44

Handle the case when pattern.length > string.length. Cost me 1 RTE.

toan_truong95: 2019-08-03 04:47:02

using go, KMP and Rabin Karp got TLE

Last edit: 2019-08-03 04:47:46
cyber_ghost002: 2019-06-30 23:17:01

applies kmp algo got ac with time 0.18

aniketsanghi: 2019-05-31 13:18:13

With Z algo in 0.2 secs

mahbubkuet08: 2019-03-24 08:08:23

Getting RTE using RobinKarp. My bad luck. :(

az2019: 2019-02-13 17:28:05

1_hashing
2_kmp
choos(e) one of them!

Last edit: 2019-02-18 18:38:36
az2019: 2019-02-13 17:27:39


Last edit: 2019-02-13 17:31:34
ameernsr: 2019-02-12 13:10:50

ac with hashing love to use kmp toooo!

ameernsr: 2019-02-12 13:10:18

badihiujattttt


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