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
janselalb: 2023-10-11 06:38:26

AC only with hashing

dawnwillcome: 2022-07-21 03:28:29

emmm RE whyyy

ayush_7901: 2022-06-08 20:09:48

submitted using Rabin Karp AC in 1 go

dineshg49: 2021-06-15 01:21:59

Very week test cases , by mistake i forgot to update my lps array in kmp algo ( later realized) and it still got AC.

parag_619: 2021-06-14 17:23:19

Used string::find and got Accepted :)

mestu_paul: 2021-04-26 10:27:33

1 go with basic kmp

kunalcodr: 2021-04-08 18:45:05

KMP 1 go.

aceash: 2021-03-13 10:34:27

Simple rabin-karp :)

shahid_92: 2021-02-02 08:48:46

First try ac
go with rabin-karp

backtobas: 2021-01-20 12:58:10

Getting tle with rabin karp help!!


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