Problem C
Sliding
You have been sent some data from the genetics department of the university. They ask you to find where in the genetic code of their mutated flies a particular mutation can be found. Since these flies are quite heftily genetically altered, their DNA has 26 possible acids rather than 4 and thus the genetic code is given by a string consisting of lower case English letters. The mutation that should be found is also given as a string of lower case English letters. We say that the mutation $S$ appears in the genetic code $T$ at location $i$ if the letters $i, i + 1, \dots , i + |S| - 1$ in $T$ contain the same letters as $S$, though possibly in a different order than in $S$. $|S|$ denotes the length of $S$.
Input
The first line of the input contains the genetic data $S$ from the flies and the second line contains the mutation $T$ that should be searched after. The string $S$ is longer than the string $T$ and the length of $S$ does not exceed $10^5$ characters.
Output
Print all locations in $S$ where the mutation $T$ occurs.
Sample Input 1 | Sample Output 1 |
---|---|
abccba bac |
1 4 |