#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

KMP Pattern Matching - Classic Problems | Repovive

CLS40. KMP Pattern Matching

2s256 MB

Given a text string $T$ and a pattern string $P$ , find all occurrences of $P$ in $T$ .

Report the total number of matches and the starting positions (1-indexed) of each occurrence.

Constraints

$1 \le |P| \le |T| \le 10^6$
Both strings contain only lowercase English letters

Input

\begin{array}{l} T \\ P \end{array}

Output

\begin{cases} k & \text{if } k = 0 \\ \begin{array}{l} k \\ p_1 \quad p_2 \quad \cdots \quad p_k \end{array} & \text{if } k > 0 \end{cases}

Samples

Input

abcabcabc
abc

Explanation

The pattern abc appears in abcabcabc starting at positions 1, 4, and 7.

Output

3
1 4 7

Input

aaaa
aa

Explanation

The pattern aa appears in aaaa starting at positions 1, 2, and 3. Overlapping matches are counted.

Output

3
1 2 3

Input

abcdef
xyz

Explanation

The pattern xyz does not appear in abcdef, so there are no positions to print.

Output

Given a text string $T$ and a pattern string $P$ , find all occurrences of $P$ in $T$ .

Report the total number of matches and the starting positions (1-indexed) of each occurrence.

$1 \le |P| \le |T| \le 10^6$
Both strings contain only lowercase English letters

\begin{array}{l} T \\ P \end{array}

\begin{cases} k & \text{if } k = 0 \\ \begin{array}{l} k \\ p_1 \quad p_2 \quad \cdots \quad p_k \end{array} & \text{if } k > 0 \end{cases}