分数: 525 点
问题陈述
对于字符串 X 长度 n,让 f(X,k) 表示重复得到的字符串 k 乘以字符串 X,和 g(X,k) 表示重复得到的字符串 k 乘第一个字符,第二个字符, \dots, n- 第一个字符 X,按此顺序。例如,如果 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