P8112 [Cnoi2021] Rune Deciphering

Cirno wants to decipher an ancient spellbook.

To protect the forbidden magic recorded in the spellbook, the author concatenated the magic affixes of spells together without spaces, forming a rune string denoted as $\texttt{S}$. All magic affixes that make up the rune string are recorded in an even older magic dictionary written by prophets, denoted as $\texttt{T}$. Specifically, all non-empty prefixes of $\texttt{T}$ are valid magic affixes. Being concise is the top priority when writing a spellbook, so the number of magic affixes used should be as small as possible. Therefore, when deciphering the spellbook, the fewer magic affixes $\texttt{S}$ is split into, the higher the chance that the deciphering is correct. Cirno wants to know the minimum number of segments when splitting this spellbook into magic affixes. In particular, if there is no valid splitting scheme, it means this spellbook is fake. Cirno will get a string `Fake`.

The first line contains two integers, representing $|\texttt{T}|$ and $|\texttt{S}|$. The second line contains a string $\texttt{T}$. The third line contains a string $\texttt{S}$.

Output one line containing an integer or a string `Fake`, representing the answer.

**Constraints and Notes** For $100\%$ of the testdata, it is guaranteed that $1 \le |\texttt{S}|, |\texttt{T}| \le 10^7$, and $\texttt{S}_x, \texttt{T}_x \in [\texttt{a},\texttt{z}]$. **Subtasks** Subtask 1 ($10$ points): $\texttt{T}_x = \texttt{a}$. Subtask 2 ($20$ points): $|\texttt{S}| \le 1000$. Subtask 3 ($30$ points): $|\texttt{S}| \le 10^6$. Subtask 4 ($40$ points): No special constraints. Translated by ChatGPT 5