AT_abc346_f [ABC346F] SSttrriinngg in StringString

对于一个长度为 $n$ 的字符串 $X$，用 $f(X,k)$ 表示将 $X$ 重复 $k$ 次得到的字符串，用 $g(X,k)$ 表示将 $X$ 的第 $1$ 个字符、第 $2$ 个字符、$\dots$、第 $n$ 个字符各重复 $k$ 次并按顺序拼接得到的字符串。例如，当 $X=$ `abc` 时，$f(X,2)=$ `abcabc`，$g(X,3)=$ `aaabbbccc`。此外，对于任意字符串 $X$，$f(X,0)$ 和 $g(X,0)$ 都是空字符串。 给定正整数 $N$ 以及字符串 $S,T$。请你求出最大的非负整数 $k$，使得 $g(T,k)$ 是 $f(S,N)$ 的（不一定连续的）子序列。注意，根据定义，$g(T,0)$ 总是 $f(S,N)$ 的子序列。 子序列指的是，从字符串 $X$ 中删除 $0$ 个或多个字符后，按原顺序连接剩下的字符所得到的字符串。例如，`ac`、`atcoder`、` `（空字符串）都是 `atcoder` 的子序列，但 `ta` 不是 `atcoder` 的子序列。

输入以如下格式从标准输入给出。 > $N$ $S$ $T$

请输出最大的非负整数 $k$，使得 $g(T,k)$ 是 $f(S,N)$ 的（不一定连续的）子序列。

## 限制条件 - $N$ 是整数 - $1\leq N\leq 10^{12}$ - $S,T$ 是仅由小写英文字母组成的字符串，长度均为 $1$ 到 $10^5$ ## 样例解释 1 $f(S,3)=$ `abcabcabc`。$g(T,2)=$ `aabb` 是 $f(S,3)$ 的子序列，但 $g(T,3)=$ `aaabbb` 不是 $f(S,3)$ 的子序列，因此输出 $2$。 由 ChatGPT 4.1 翻译