题意

从字符串\(A\)中取出可空子串\([l1,r1]\),从字符串\(B\)中取出可空子串\([l2,r2]\),要求\(r1=l2\)且长度最长。

分析

假设是字符串\(A\)的子串比较长,那么这个一段子串的最后一定是一个回文串,而且是这个回文串中心的最大回文串(可以显然的看出,如果不是最长的回文串对于这道题目是没有意义的)

这样一来。我们对于所以位置的最大回文串,在继续匹配这一段子串的前面和字符串\(B\)子串最后一个位置开始的最大匹配量,可以用 hash + 二分 来解决。

当然可能是\(B\)的长度大于\(A\),两个字符串分别倒置,在做一遍就可以了。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注