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
Abhishek:
20160927 10:36:47
Curious as to what people doing it in 0.01 are using? KMP , Z or RabinKarp?


adichd123:
20160704 18:45:25
Same as NHAY!! 

azam_9:
20160622 21:24:16
A.C. in .06s..Brute force rock.. 

mkfeuhrer:
20160618 22:16:29
my first implementation of kmp algo !! :) AC in one go .. 

flyingduchman_:
20160616 18:13:06
I used [spoiler removed] algorithm Last edit: 20160616 20:12:44 

bholagabbar:
20160506 19:26:32
Incase you're getting a WA in rabin karp, check for the condition where subtracting a value makes your hash negative. In that case, you'll have to add the mod to make it positive 

darkhire21:
20160131 08:37:57
check test case


[Mayank Pratap]:
20151019 09:17:07
After 3 WAs I solved this using Rabinkarp :) 

[Mayank Pratap]:
20151015 10:22:13
Weak test cases ..


Oasis:
20150804 18:55:07
i dont understand y my brute force solution is better than kmp......

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