Find All Anagrams in a String

Given two strings \(s\) and \(p\), find all the starting indices in \(s\) where the substring is an anagram of \(p\). An anagram is a rearrangement of letters; formally, two strings \(x\) and \(y\) are anagrams if and only if \(\text{count}(x) = \text{count}(y)\) where \(\text{count}(z)\) denotes the frequency count of each character in \(z\).

The algorithm should work by employing a sliding window of size \(|p|\) over the string \(s\) and comparing character frequencies with that of \(p\). In mathematical terms, if \(|s|\) is the length of the string \(s\) and \(|p|\) is the length of the pattern \(p\), then for every index \(i\) from \(0\) to \(|s| - |p|\), check if

[ \text{Counter}(s[i \ldots i+|p|-1]) = \text{Counter}(p) ]

If the above holds, then index \(i\) is part of the answer. Return all such indices in ascending order.

inputFormat

The input is read from stdin and consists of exactly two lines:

• The first line contains the string \(s\).
• The second line contains the string \(p\), which is the pattern.

outputFormat

Output the starting indices (0-indexed) of all anagrams of \(p\) in \(s\) in ascending order, separated by a single space. If there are no such indices, output an empty line.

cbaebabacd
abc

0 6