题目描述

给定两个均由小写英文字母组成的字符串 $s$ 和 $t$。数据保证字符串 $t$ 是字符串 $s$ 的一个子序列。

现在你需要从字符串 $s$ 中删除一个最长的连续子序列（剩余的两部分在不变换顺序的情况下再拼接起来），并得到一个剩余的字符串 $s'$，并且你还需要保证字符串 $t$ 仍然是剩余的字符串 $s'$ 的一个子序列。

举个例子，比如说你删除的是子串 $s[l..r]$，那么你要保证字符串 $t$ 仍然是剩余的字符串 $s_1 s_2 \dots s_{l-1} s_{r+1} s_{r+2} \dots s_{|s|-1} s_{|s|}$ 的一个子序列（这里 $|s|$ 表示字符串 $s$ 的长度）。

求：你能够删除的那个子串的最大长度。

输入格式

第一行，一个字符串 $s$。

第二行，一个字符串 $t$。

数据保证字符串长度不超过 $2 \cdot 10^5$ 且字符串 $t$ 是字符串 $s$ 的一个子串。

输出格式

输出一个整数，表示能够删除的子串的最大长度。

bbaba
bb

3

quanjun
qun

4

wanglaoshizhenshuai
wlszs

4

说明/提示

数据规模与约定

设 $|s|$ 表示字符串 $s$ 的长度，则：

• 对于 $30\%$ 的数据，$|s| \le 20$
• 对于 $50\%$ 的数据，$|s| \le 200$
• 对于 $80\%$ 的数据，$|s| \le 2000$
• 对于 $100\%$ 的数据，$1 \le |s| \le 2 \cdot 10^5$