SSttrriinngg in StringString

题目描述

对于长度为 $n$ 的字符串 $X$,定义 $f(X,k)$ 为将字符串 $X$ 重复 $k$ 次得到的字符串,定义 $g(X,k)$ 为将 $X$ 的第 1 个字符、第 2 个字符、……、第 $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$ 的一个(不必连续的)子序列是指,从 $X$ 中删除零个或多个字符后,将剩余字符按原顺序拼接得到的字符串。 例如,ac、atcoder 和空字符串都是 atcoder 的子序列,但 ta 不是。

输入格式

输入按以下格式从标准输入给出:

$N$
$S$
$T$

输出格式

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

样例

3
abc
ab

2

有 $f(S,3)=$ abcabcabc。 $g(T,2)=$ aabb 是 $f(S,3)$ 的子序列,但 $g(T,3)=$ aaabbb 不是,因此输出 $2$。

3
abc
arc

0

1000000000000
kzazkakxkk
azakxk

344827586207

数据范围

• $N$ 是整数。
• $1 \leq N \leq 10^{12}$
• $S$ 和 $T$ 是由小写英文字母组成的字符串,长度在 $1$ 到 $10^5$ 之间(含两端)。