SSttrriinngg in StringString

题目描述

对于长度为 $n$ 的字符串 $X$，记 $f(X,k)$ 为将字符串 $X$ 重复 $k$ 次得到的字符串，记 $g(X,k)$ 为按顺序将 $X$ 的第一个字符重复 $k$ 次、第二个字符重复 $k$ 次、…、第 $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)$ 的子序列。

输入格式

输入按下列格式由标准输入给出： $N$ $S$ $T$

输出格式

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

3
abc
ab

2

3
abc
arc

0

1000000000000
kzazkakxkk
azakxk

344827586207

提示

$N$ 是一个整数。 $1\leq N\leq 10^{12}$ $S$ 和 $T$ 是由小写英文字母组成的字符串，长度在 $1$ 到 $10^5$（含）之间。我们有 $f(S,3)=abcabcabc$。 $g(T,2)=aabb$ 是 $f(S,3)$ 的一个子序列，但 $g(T,3)=aaabbb$ 不是，所以输出 $2$。

标签: AtCoder|abc346F

来源

AtCoder|abc346F