AT_abc346_f.[ABC346F] SSttrriinngg in StringString

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

对于一个长度为 $n$ 的字符串 $X$ ，用 $f(X,k)$ 表示将 $X$ 重复 $k$ 次得到的字符串，用 $g(X,k)$ 表示将 $X$ 的第 $1$ 个字符、第 $2$ 个字符、 $\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$ 中删除 $0$ 个或多个字符后，按原顺序连接剩下的字符所得到的字符串。例如，ac、atcoder、（空字符串）都是 atcoder 的子序列，但 ta 不是 atcoder 的子序列。

输入格式

输入以如下格式从标准输入给出。

$N$ $S$ $T$

输出格式

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

输入输出样例

输入#1
```
3
abc
ab
```
输出#1
```
2
```
输入#2
```
3
abc
arc
```
输出#2
```
0
```

输入#3

1000000000000
kzazkakxkk
azakxk

输出#3

344827586207

说明/提示

限制条件

$N$ 是整数
$1\leq N\leq 10^{12}$
$S,T$ 是仅由小写英文字母组成的字符串，长度均为 $1$ 到 $10^5$

样例解释 1

$f(S,3)=$ abcabcabc。 $g(T,2)=$ aabb 是 $f(S,3)$ 的子序列，但 $g(T,3)=$ aaabbb 不是 $f(S,3)$ 的子序列，因此输出 $2$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页