684. Where Every Rearrangement Appears
Given a string s and a pattern p, print every starting index in s at which
some rearrangement of p appears. Indices are 0-based and printed in increasing
order. Print none if there is no such index.
Problem #75 asks whether two whole strings are rearrangements of each other. This
asks WHERE one occurs inside another, which is the version interviews use,
because the naive answer is O(n * m log m) and the window is O(n).
The window here has a FIXED width, the length of p, which makes it simpler than
the growing windows above. Slide it one position at a time: add the character
entering on the right, remove the one leaving on the left, and the window is a
match whenever its 26 counts equal the pattern's.
Sorting each window would be correct and far too slow. The counts change by exactly two entries per step, so there is no reason to rebuild them.
Constraints - `1 ≤ length of s ≤ 100000` - `1 ≤ length of p ≤ 100000` - Both strings contain only the characters `a` to `z`.
Input
The first line contains the string s.
The second line contains the pattern p. Both are lowercase English letters.
Output
Print the 0-based starting indices in increasing order, separated by single spaces, or none if there are none.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.