← 返回题目列表

AtCoder · abc346_f

I. StringString 中的 SSttriingg

中文机器翻译题面 查看原题

分数: 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