103465: [Atcoder]ABC346 F - SSttrriinngg in StringString
Description
Score: $525$ points
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
Input
Output
分数：$525$分
问题描述
对于长度为$n$的字符串$X$，令$f(X,k)$表示重复$k$次字符串$X$得到的字符串，令$g(X,k)$表示按照顺序重复$k$次$X$的第一个字符、第二个字符、$\dots$、第$n$个字符得到的字符串。例如，如果$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$是一个整数。
- $1\leq N\leq 10^{12}$
- $S$和$T$是由小写英文字母组成的字符串，长度在$1$到$10^5$之间（含）。
输入
输入通过标准输入给出，如下所示：
$N$ $S$ $T$
输出
打印最大的非负整数$k$，使得$g(T,k)$是$f(S,N)$的（不一定连续的）子序列。
样例输入1
3 abc ab
样例输出1
2
我们有$f(S,3)=$abcabcabc。
$g(T,2)=$aabb是$f(S,3)$的子序列，但$g(T,3)=$aaabbb不是，所以打印$2$。
样例输入2
3 abc arc
样例输出2
0
样例输入3
1000000000000 kzazkakxkk azakxk
样例输出3
344827586207