Score: $525$ points

问题陈述

对于长度为 $n$ 的字符串 $X$，让 $f(X,k)$ 表示通过重复字符串 $X$ 来获得的字符串 $k$ 次，让 $g(X,k)$ 表示通过重复字符串 $X$ 的第一个字符、第二个字符、$\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$ 的（不一定是连续的）子序列是通过从 $X$ 中删除零个或多个字符，然后不改变顺序地连接剩余元素而获得的字符串。例如，ac、atcoder 和（空字符串）都是 atcoder 的子序列，但 ta 不是。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

For a string $X$ of length $n$, let $f(X,k)$ denote the string obtained by repeating $k$ times the string $X$, and $g(X,k)$ denote the string obtained by repeating $k$ times the first character, the second character, $\dots$, the $n$-th character of $X$, in this order. For example, if $X=$ abc, then $f(X,2)=$ abcabc, and $g(X,3)=$ aaabbbccc. Also, for any string $X$, both $f(X,0)$ and $g(X,0)$ are empty strings.

You are given a positive integer $N$ and strings $S$ and $T$. Find the largest non-negative integer $k$ such that $g(T,k)$ is a (not necessarily contiguous) subsequence of $f(S,N)$. Note that $g(T,0)$ is always a subsequence of $f(S,N)$ by definition.

What is a subsequence? A (not necessarily contiguous) subsequence of a string $X$ is a string obtained by removing zero or more characters from $X$ and then concatenating the remaining elements without changing the order. For example, ac, atcoder, and (empty string) are all subsequences of atcoder, but ta is not.

Constraints

• $N$ is an integer.
• $1\leq N\leq 10^{12}$
• $S$ and $T$ are strings consisting of lowercase English letters with lengths between $1$ and $10^5$, inclusive.

Input

The input is given from Standard Input in the following format:

$N$

$S$

$T$

Output

Print the largest non-negative integer $k$ such that $g(T,k)$ is a (not necessarily contiguous) subsequence of $f(S,N)$.

Sample Input 1

3
abc
ab

Sample Output 1

2

We have $f(S,3)=$ abcabcabc. $g(T,2)=$ aabb is a subsequence of $f(S,3)$, but $g(T,3)=$ aaabbb is not, so print $2$.

Sample Input 2

3
abc
arc

Sample Output 2

0

Sample Input 3

1000000000000
kzazkakxkk
azakxk

Sample Output 3

344827586207

update @ 2024/5/16 17:18:22