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
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 _/\_
|
|
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?
|
|
adichd123:
2016-07-04 18:45:25
Same as NHAY!! |
|
azam_9:
2016-06-22 21:24:16
A.C. in .06s..Brute force rock.. |
|
mkfeuhrer:
2016-06-18 22:16:29
my first implementation of kmp algo !! :-) AC in one go .. |
|
flyingduchman_:
2016-06-16 18:13:06
I used [spoiler removed] algorithm Last edit: 2016-06-16 20:12:44 |
|
bholagabbar:
2016-05-06 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 |
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 |