Z Algorithm For Pattern Searching

hard
Question Solve Solutions 
1. You are given two strings s1 and s2.
2. s1 represents a text and s2 represents a pattern. 
3. You have to print the starting index for all occurrences of the pattern in the given text string.

Input Format

Two strings s1 and s2 in two different lines.

Output Format

Starting index for all occurrences of the pattern in the given text string.

Constraints

1 <= length of the strings <= 10^4

Example

Input
abab
ab
Output
0
2
Previous
Kmp Pattern Searching
Next
Find String Roots

Related Questions

easy Shortest Palindrome medium Longest Palindromic Substring hard Kmp Pattern Searching hard Find String Roots hard Manacher's Algorithm hard String Rotation hard Prefix And Suffix Count medium Say No To Palindrome medium String Polynomial Hashing medium Diane medium Rabin Karp Pattern Find (spoj) hard Password medium Good Substrings hard Longest Duplicate Substring medium Longest Prefix Suffix hard Lexicographical Suffixes