DSA Level 3 Competitive Text Processing Kmp Pattern Searching

Kmp Pattern Searching

hard

Text Processing

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 &lt;= length of the strings &lt;= 10^4

Example

Input

abab
ab

Output

0
2

Longest Palindromic Substring

Z Algorithm For Pattern Searching

Related Questions

easy Shortest Palindrome medium Longest Palindromic Substring hard Z Algorithm For 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