#A. 2023.08.27-ZJTD秋招第二场-第一题-相似字符串

    Type: Default 1000ms 256MiB

2023.08.27-ZJTD秋招第二场-第一题-相似字符串

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目内容

给定两个字符串ss , tt

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

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

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

现在塔子哥可以进行最多一次修改: ss的一个小写字母改成另一个小写字母,使得相似度f(s,t)f(s,t)尽量大,请输出这个相似度!

输入描述

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

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

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

输出描述

输出一个整数。

样例

输入

bad
baab

输出

4

说明

ss串的第三个字符改成'bb',s串变成"babbab"。最长相同前缀和后缀分别是"baba"和"abab"。