P8112 [Cnoi2021] 符文破译

Cirno 想要解读一本古老的魔法书。

为了保护魔法书中记载的禁忌的魔法，撰写者将符咒的魔法词缀不加空格地连接在一起，形成一个符文串，记作 $\texttt{S}$。 而构成符文串的所有魔法词缀都被记载在更远古的先知所编写的魔法辞典中，记作 $\texttt{T}$。具体地，$\texttt{T}$ 的所有非空前缀均是一个合法的魔法词缀。 简洁是魔法书撰写的第一要务，所以使用的魔法词缀应该尽可能少。所以在破译魔法书时，将 $\texttt{S}$ 分解成的魔法词缀数越少，破译正确的可能性就越高。 Cirno 想知道，这本魔法书最少的魔法词缀划分段数是多少。 特别地，如果不存在一种合法的划分方案，则表明这本魔法书是假的。Cirno 将得到一个字符串 `Fake`。

无

无

**数据范围与约定** 对于 $100\%$ 的数据，保证 $1\le |\texttt{S}|,|\texttt{T}|\le 10^7$，$\texttt{S}_x,\texttt{T}_x \in [\texttt{a},\texttt{z}]$。 **子任务** Subtask1（$10$ points）：$\texttt{T}_x=\texttt{a}$。 Subtask2（$20$ points）：$|\texttt{S}|\le1000$。 Subtask3（$30$ points）：$|\texttt{S}|\le 10^6$。 Subtask4（$40$ points）：无特殊限制。