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
|
asifalim:
2020-05-09 13:49:20
using kmp O(n+m) 0.38 sec
|
|
medhruv7:
2020-05-01 14:30:01
rabin karp AC one go :) |
|
riyansh16_:
2020-04-14 21:11:43
can be done by brute force with a time complexity of O(n)
|
|
alphatheta:
2020-04-05 23:48:27
AC with Polynomial Hashing: 0.24s |
|
pandey101299:
2019-12-02 18:02:13
with Z algo in 0.19 secs
|
|
pumpkinduke:
2019-11-14 18:27:48
Guys beware of giving the space between numbers.it cost me many WA -___- |
|
fardin_abir:
2019-10-31 08:09:37
ac with kmp in .16 s |
|
tpriyanshu:
2019-10-15 03:02:07
If you are doing rabin-karp, and getting TLE, make sure you take care of the case when hash becomes -ve. Simply add mod to it. |
|
magetron:
2019-09-08 14:32:08
test case is rather weak, submiited a wrong solution and got accepted
|
|
mostafa_haamed:
2019-08-21 21:43:00
ac from first hit using z algorithm |
| 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