题目内容

给定两个字符串$s$ , $t$

$lcp(s,t)$ : 最长相同前缀长度

$lcs(s,t)$ : 最长相同后缀长度

$f(s,t) = lcp(s,t) * lcs(s , t)$ ： 字符串相似度

现在小红可以进行最多一次修改： $s$的一个小写字母改成另一个小写字母，使得相似度$f(s,t)$尽量大，请输出这个相似度！

输入描述

第一行输入一个仅包含小写字母的字符串s。

第二行输入一个仅包含小写字母的字符串t。

$1 \leq len(s),len(t) \leq 1e5$

输出描述

输出一个整数。

样例

输入

bad
baab

输出

4

说明

将$s$串的第三个字符改成'$b$'，s串变成"$bab$"。最长相同前缀和后缀分别是"$ba$"和"$ab$"。

思路:模拟

由于题目说只能改一次，所以我们可以很暴力的去解决这个问题：枚举改的这一次到底使用在哪？

我们要使用修改机会，只会在这两种情况下：

1.修改使得LCS更大

2.修改使得LCP更大