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

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

题目内容

给定两个字符串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。

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

输出描述

输出一个整数。

样例

输入

bad
baab

输出

4

说明

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

知识点:*****

查看知识点以及同类型题目

Statistics

Related

In following contests:

秋招模拟赛第41场|2023.08.27-字节跳动秋招第二场