题目描述

题目译自 XXVII Olimpiada Informatyczna – Eliminacje do IOI Szyld

Bajtazar 即将开设一家新的批发商店。他希望在入口上方悬挂一个巨大的招牌，上面写着某个特定的文字。这个文字应当尽可能多次包含他公司的名称作为连续的片段，且这些片段可以相互重叠。

凭借过往经验，Bajtazar 知道必须提防破坏招牌的破坏者。他担心一些流氓可能会尝试涂抹招牌上的某些字母，使得剩下的（未被涂抹的）字母恰好组成竞争对手公司的名称。因此，他希望设计一个招牌文字，使这种破坏行为无法实现。

你能帮助他吗？

输入格式

输入数据包含两行：第一行是一个字符串，表示 Bajtazar 公司的名称；第二行是一个字符串，表示竞争对手公司的名称。这两个字符串均非空，由英文小写字母、大写字母和/或数字组成。注意：在比较字符串时，区分大小写。

输出格式

输出只有一行：如果有限，应为一个整数，表示满足任务条件的前提下，招牌文字中 Bajtazar 公司名称的最大出现次数；如果 Bajtazar 公司名称可以在招牌文字中出现无限多次，则输出字符串 INF。

karolek
lololek

2

Bajtazar 可以选择招牌文字为 karolekarolek。如果将 karolek 放置三次于招牌上，则不可避免地存在一种涂抹方式，使得剩余的字母组成 lololek。

附加样例

1. 字符串为 $\texttt{abababab}$ 和 $\texttt{bbbbbbbbbbbb}$，答案为 $7$；
2. 第一个字符串包含每个可能的字母和数字各一次，第二个字符串为 $\texttt{43210}$，答案为 $4$；
3. 第一个字符串为 $\texttt{a}^{999999} \texttt{b}$，第二个字符串为 $\texttt{a}^{1000000}$，答案为 $1$。

数据范围与提示

令 $n$ 表示两个公司名称长度的限制。详细子任务附加限制及分值如下表所示。