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| ≤ 106
All character will be lowercase Latin character. And | | is the length of string.
Output
For each case print the number (found pattern from the given string) next line their positions. Otherwise print 'Not Found' without quotes.
Output a blank line between two cases.
Example
Input: 3 ababab ab aaaaa bbb aafafaasf aaf Output: 3 1 3 5 Not Found 1 1
Hints: Here all index is 1 based.
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 |
RSS