题目描述

Giorgio 想用报纸上的文字拼出一张便条。

给定目标字符串 $N$ 和报纸字符串 $S$。每次操作可以从 $S$ 中剪下一段连续子串，并把它粘到便条末尾。由于 Giorgio 有很多份同样的报纸，不同剪下的片段可以相互重叠，也可以重复使用。

请用尽量少的连续子串，将它们依次拼接成字符串 $N$。

输入格式

第一行是目标字符串 $N$。

第二行是报纸字符串 $S$。

两行均可能包含空格和其他 ASCII 可打印字符。

输出格式

输出一个整数，表示最少需要剪下多少段子串。

数据范围

• $N,S$ 只包含 ASCII 可打印字符；
• $1\le |N|\le1\,000\,000$；
• $1\le |S|\le10\,000$；
• 保证可以由 $S$ 的若干子串拼出 $N$。

子任务

1. 样例，5 分；
2. $N$ 由同一个字符重复构成，10 分；
3. $|N|,|S|\le20$，20 分；
4. $|N|\le1000$，25 分；
5. $|S|\le1000$，25 分；
6. 无额外限制，15 分。

样例 1

@dd10 v1cin *
0 v@d1ci * n

6

一种最优拼法为：@d、d1、0 v、1ci、n、*。

样例 2

caro vicino vuoi smetterla di fare casino
Il caro vita sale ancora : se sei mancino vuoi smettere di comprare oggetti appositi , per esempio . Fare cassa e ' sempre piu ' difficile ; parola di fiscalista .

5