← 返回题目列表

Codeforces · 1492/C

C. 最大宽度

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

你的同学,你不喜欢他,因为他很无聊,但你尊重他的才智,他有两个字符串:长度为 $$$n$$$ 的 $$$s$$$ 和长度为 $$$m$$$ 的 $$$t$$$。

序列 $$$p_1, p_2, \ldots, p_m$$$,其中 $$$1 \leq p_1 < p_2 < \ldots < p_m \leq n$$$,如果 $$$s_{p_i} = t_i$$$ 对于从 $$$1$$$ 到 $$$m$$$ 的所有 $$$i$$$ 来说是美丽的。序列的宽度定义为 $$$\max\limits_{1 \le i < m} \left(p_{i + 1} - p_i\right)$$$。

请帮助你的同学找出最大宽度的美丽序列。你的同学向你保证,对于给定的字符串 $$$s$$$ 和 $$$t$$$ 至少有一个漂亮的序列。

输入

第一个输入行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq m \leq n \leq 2 \cdot 10^5$$$) - 字符串 $$$s$$$ 和 $$$t$$$ 的长度。

以下行包含长度为 $$$n$$$ 的单个字符串 $$$s$$$,由拉丁字母表的小写字母组成。

最后一行包含一个长度为 $$$m$$$ 的字符串 $$$t$$$,由拉丁字母的小写字母组成。

保证给定的字符串至少有一个漂亮的序列。

输出

输出一个整数——一个漂亮序列的最大宽度。

示例

输入 #1

5 3
abbbc
abc

输出 #1

3

输入 #2

5 2
aaaaa
aa

输出 #2

4

输入 #3

5 5
abcdf
abcdf

输出 #3

1

输入#4

2 2
ab
ab

输出#4

1

注意

在第一个示例中,有两个漂亮的宽度 $$$3$$$ 序列:它们是 $$$\{1, 2, 5\}$$$ 和 $$$\{1, 4, 5\}$$$。

在第二个示例中,最大宽度的美丽序列是 $$$\{1, 5\}$$$。

在第三个示例中,有一个漂亮的序列 - 它是 $$$\{1, 2, 3, 4, 5\}$$$。

在第四个示例中,有一个漂亮的序列 - 它是 $$$\{1, 2\}$$$。