Loading...
Loading...
Loading...
Ananya's college library scans old question papers into one long line of lowercase letters, with no spaces. She types a word into the search box and wants every place where that word starts.
Matches may overlap. In the text aaaa, the word aa starts at positions 1, 2 and 3.
Print how many times the pattern appears in the text, and then all its start positions.
Example 1
Input
abababa aba
Output
3 1 3 5
aba starts at positions 1, 3 and 5. The matches at 1 and 3 share the letter at position 3.
Example 2
Input
rollnumber rolls
Output
0
The pattern never appears, so only 0 is printed.
Try the problem first. Open one hint at a time.
Comparing the pattern at every start position from scratch can cost text length × pattern length steps, far too slow for 10^6 letters.
When a comparison fails after some matched letters, those letters are already known. Use them instead of moving back in the text.
For every prefix of the pattern, store the length of its longest proper prefix that is also its suffix. On a mismatch, jump to that length.
After a full match, do not reset to 0. Jump to the stored value for the whole pattern, so overlapping matches are found too.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor