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.

\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}

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.

\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}