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 
3 
Hints:
hide comments
rehank478:
20200628 19:14:26
AC in one go using Rabin Karp 

fawad:
20200623 08:12:45
Learned both rabin karp and kmp :) 

arpit_pro:
20200530 20:06:46
weak test cases I later came to know that my code was wrong but it passed 

nb_3018:
20200528 18:58:36
I'm getting TLE inspite of using the KMP algorithm (coded in Java), can't figure out why ... 

lovlesh_007:
20200525 09:33:52
Using string find function , I get the Time complexity of 0.02 seconds. 

asifalim:
20200509 13:49:20
using kmp O(n+m) 0.38 sec


medhruv7:
20200501 14:30:01
rabin karp AC one go :) 

riyansh16_:
20200414 21:11:43
can be done by brute force with a time complexity of O(n)


alphatheta:
20200405 23:48:27
AC with Polynomial Hashing: 0.24s 

pandey101299:
20191202 18:02:13
with Z algo in 0.19 secs

Added by:  Najmuzzaman 
Date:  20141023 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 